Teoria De Graficas
Páginas: 6 (1301 palabras)
Publicado: 23 de enero de 2013
8 TEORIA DE GRAFICAS
Una grafica no dirigida G, consiste en un conjunto de V de vértices o nodos y un conjunto E de aristas o arcos, tal que cada arista e ( E se asocia con un par no ordenado de vértices.
[pic]
Una grafica dirigida G, consiste en un conjunto de V de vértices o nodos y un conjunto E de aristas o arcos, tal que cada arista e ( E se asocia con un par ordenado de vértices.[pic]
Los vértices son los puntos o pequeños círculos y las líneas que conectan a los vértices se llaman aristas, las aristas dirigidas se indican por flechas.
Las aristas asociadas a un mismo par de vértices se llaman aristas paralelas, si una arista incidente en un mismo vértice se llama lazo y cuando un vértice no incide en ninguna arista, se llama vértice aislado.
Una grafica sinlazos ni aristas paralelas se llama grafica simple.
Si se inicia en un vértice v0, enseguida se viaja por una arista al vértice v1, después por otra arista al vértice v2, etcétera, y con el tiempo se llega al vértice vn; este viaje completo recibe el nombre de trayectoria o ruta de v0 a vn. Formalmente si v0 y vn son vértices de una grafica, una trayectoria de v0 a vn de longitud n es una sucesiónalternante de n+1 vértices y n aristas que comienza en el vértice v0 y termina en el vértice vn.
[pic]
Una grafica con números en las aristas se llama grafica ponderada o con peso, si la arista e se etiqueta k, se dice que el peso de la arista e es k.
En una grafica ponderada, la longitud de una ruta es la suma de los pesos de las aristas en la ruta.
La grafica completa sobre nvértices, denotada por Kn, es la grafica simple con n vértices en la que hay una arista entre cada par de vértices.
[pic]
Una grafica G = (V, E) es bipartita si existen subconjuntos V1 y V2 de V tales que V1 ( V2 = (, V1 ( V2 = V, y cada arista en E es incidente sobre un vértice en V1 y un vértice en V2.
[pic]
Una grafica bipartita completa sobre m y n vértices, denotada por Km, n, es la graficasimple donde el conjunto de vértices tiene una partición V1 con m vértices y V2 con n vértices y donde el conjunto de aristas consiste en todas las aristas de la forma (v1, v2) con v1 ( V1 y v2 ( V2.
[pic]
Una grafica conexa es una grafica en la que se puede ir de cualquier vértice a cualquier otro vértice por una trayectoria, formalmente una grafica G es conexa si dados cualesquiera dosvértices v y w, existe una trayectoria de v a w.
[pic]
Una grafica conexa es de una pieza, mientras que una grafica no conexa consiste en varias piezas. Estas piezas son subgraficas de la grafica original y se llaman componentes.
Una subgrafica G’ de una grafica G se obtiene seleccionando ciertas aristas y vértices de G sujetas a la restricción de que si se selecciona una arista e en G que incideen los vértices v y w, deben incluirse v y w en G’.
Sean v y w vértices en una grafica G.
Una trayectoria simple de v a w es una ruta de v a w sin vértices repetidos.
Un ciclo o circuito es una trayectoria de longitud diferente de cero de v a v sin aristas repetidas.
Un ciclo simple es un ciclo de v a v en el que no hay vértices repetidos, excepto por el inicio yel fin que son iguales a v.
Un ciclo en una grafica G que incluye todas las aristas y todos los vértices de G se llama ciclo de Euler.
Grado de un vértice v, δ(v), es el número de aristas que inciden en v.
Si una grafica G tiene un ciclo de Euler, entonces G es conexa y todo vértice tiene grado par.
[pic]
Un ciclo en una grafica G que contiene cada vértice en G justo una vez, excepto porel vértice inicial y final que aparece dos veces, recibe el nombre de ciclo hamiltoniano.
[pic]
Ruta mas corta es la longitud mas corta del vértice a al z, existen algoritmos preestablecidos para encontrarla.
[pic]
Matriz de adyacencia, para obtener esta matriz, primero se selecciona un orden de los vértices, después se etiquetan los renglones y columnas de una matriz con los...
Una grafica no dirigida G, consiste en un conjunto de V de vértices o nodos y un conjunto E de aristas o arcos, tal que cada arista e ( E se asocia con un par no ordenado de vértices.
[pic]
Una grafica dirigida G, consiste en un conjunto de V de vértices o nodos y un conjunto E de aristas o arcos, tal que cada arista e ( E se asocia con un par ordenado de vértices.[pic]
Los vértices son los puntos o pequeños círculos y las líneas que conectan a los vértices se llaman aristas, las aristas dirigidas se indican por flechas.
Las aristas asociadas a un mismo par de vértices se llaman aristas paralelas, si una arista incidente en un mismo vértice se llama lazo y cuando un vértice no incide en ninguna arista, se llama vértice aislado.
Una grafica sinlazos ni aristas paralelas se llama grafica simple.
Si se inicia en un vértice v0, enseguida se viaja por una arista al vértice v1, después por otra arista al vértice v2, etcétera, y con el tiempo se llega al vértice vn; este viaje completo recibe el nombre de trayectoria o ruta de v0 a vn. Formalmente si v0 y vn son vértices de una grafica, una trayectoria de v0 a vn de longitud n es una sucesiónalternante de n+1 vértices y n aristas que comienza en el vértice v0 y termina en el vértice vn.
[pic]
Una grafica con números en las aristas se llama grafica ponderada o con peso, si la arista e se etiqueta k, se dice que el peso de la arista e es k.
En una grafica ponderada, la longitud de una ruta es la suma de los pesos de las aristas en la ruta.
La grafica completa sobre nvértices, denotada por Kn, es la grafica simple con n vértices en la que hay una arista entre cada par de vértices.
[pic]
Una grafica G = (V, E) es bipartita si existen subconjuntos V1 y V2 de V tales que V1 ( V2 = (, V1 ( V2 = V, y cada arista en E es incidente sobre un vértice en V1 y un vértice en V2.
[pic]
Una grafica bipartita completa sobre m y n vértices, denotada por Km, n, es la graficasimple donde el conjunto de vértices tiene una partición V1 con m vértices y V2 con n vértices y donde el conjunto de aristas consiste en todas las aristas de la forma (v1, v2) con v1 ( V1 y v2 ( V2.
[pic]
Una grafica conexa es una grafica en la que se puede ir de cualquier vértice a cualquier otro vértice por una trayectoria, formalmente una grafica G es conexa si dados cualesquiera dosvértices v y w, existe una trayectoria de v a w.
[pic]
Una grafica conexa es de una pieza, mientras que una grafica no conexa consiste en varias piezas. Estas piezas son subgraficas de la grafica original y se llaman componentes.
Una subgrafica G’ de una grafica G se obtiene seleccionando ciertas aristas y vértices de G sujetas a la restricción de que si se selecciona una arista e en G que incideen los vértices v y w, deben incluirse v y w en G’.
Sean v y w vértices en una grafica G.
Una trayectoria simple de v a w es una ruta de v a w sin vértices repetidos.
Un ciclo o circuito es una trayectoria de longitud diferente de cero de v a v sin aristas repetidas.
Un ciclo simple es un ciclo de v a v en el que no hay vértices repetidos, excepto por el inicio yel fin que son iguales a v.
Un ciclo en una grafica G que incluye todas las aristas y todos los vértices de G se llama ciclo de Euler.
Grado de un vértice v, δ(v), es el número de aristas que inciden en v.
Si una grafica G tiene un ciclo de Euler, entonces G es conexa y todo vértice tiene grado par.
[pic]
Un ciclo en una grafica G que contiene cada vértice en G justo una vez, excepto porel vértice inicial y final que aparece dos veces, recibe el nombre de ciclo hamiltoniano.
[pic]
Ruta mas corta es la longitud mas corta del vértice a al z, existen algoritmos preestablecidos para encontrarla.
[pic]
Matriz de adyacencia, para obtener esta matriz, primero se selecciona un orden de los vértices, después se etiquetan los renglones y columnas de una matriz con los...
Leer documento completo
Regístrate para leer el documento completo.