Teoria de grafos
Páginas: 4 (920 palabras)
Publicado: 6 de agosto de 2010
Departamento Académico: Lic. Ejecutiva
Asignatura: Teoría de la Computacion
TEORÍA DE GRAFOS
Grafos. Conceptos fundamentales
Un grafo G es un par G = (V,E), donde V es un conjunto finito(vértices, nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados por {x, y}, que se denominan lados, aristas, etc. En este caso decimos que x y y son extremos de {x, y}. Denotamos V(G) por el conjunto de vértices del grafo G y por E(G) el conjunto de lados del grafo G. Además º(G) y "(G) denotan el número de vértices y el número de aristas de G respectivamente. Puesto que E esun multiconjunto es posible que existen pares repetidos, en este caso G tiene lados múltiples. También es posible que algún par no ordenado de E tenga el mismo vértice repetido, en este caso decimosque el lado es un lazo (loop) o bucle . Cuando existen lados múltiples y/o lazos decimos que G es un multigrafo. Si no hay lados múltiples ni lazos decimos que es un grafo simple. Un digrafo G es unpar G = (V,E) donde V es un conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como vértice inicial a u ycomo vértice terminal a v.
A continuación damos unas definiciones que provienen del libro de Matemá- ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las diferentesdefiniciones.
Definición 1 Un grafo simple G(V,E) consta de V , un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenados de elementos distintos de V . A esos pares se les llamaaristas o lados.
Definición 2 Un multigrafo G(V,E) consta de un conjunto V de vertices, un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Se dice que las aristas e1, e2 sonaristas múltiples o paralelas si f(e1) = f(e2).
Los multigrafos definidos no admiten bucles o lazos (aristas que conectan un vértice consigo mismo). Usamos en este caso, pseudografos que son más...
Asignatura: Teoría de la Computacion
TEORÍA DE GRAFOS
Grafos. Conceptos fundamentales
Un grafo G es un par G = (V,E), donde V es un conjunto finito(vértices, nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados por {x, y}, que se denominan lados, aristas, etc. En este caso decimos que x y y son extremos de {x, y}. Denotamos V(G) por el conjunto de vértices del grafo G y por E(G) el conjunto de lados del grafo G. Además º(G) y "(G) denotan el número de vértices y el número de aristas de G respectivamente. Puesto que E esun multiconjunto es posible que existen pares repetidos, en este caso G tiene lados múltiples. También es posible que algún par no ordenado de E tenga el mismo vértice repetido, en este caso decimosque el lado es un lazo (loop) o bucle . Cuando existen lados múltiples y/o lazos decimos que G es un multigrafo. Si no hay lados múltiples ni lazos decimos que es un grafo simple. Un digrafo G es unpar G = (V,E) donde V es un conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como vértice inicial a u ycomo vértice terminal a v.
A continuación damos unas definiciones que provienen del libro de Matemá- ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las diferentesdefiniciones.
Definición 1 Un grafo simple G(V,E) consta de V , un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenados de elementos distintos de V . A esos pares se les llamaaristas o lados.
Definición 2 Un multigrafo G(V,E) consta de un conjunto V de vertices, un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Se dice que las aristas e1, e2 sonaristas múltiples o paralelas si f(e1) = f(e2).
Los multigrafos definidos no admiten bucles o lazos (aristas que conectan un vértice consigo mismo). Usamos en este caso, pseudografos que son más...
Leer documento completo
Regístrate para leer el documento completo.