Circuito y camino eurelino

RESUMEN DEL CAPÍTULO VIII LIBRO MATEMÁTICA DISCRETA Y SUS APLICACIONES QUINTA EDICIÓN DE KENNETH H. ROSEN

DAVID RIVILLAS

MATEMÁTICAS DISCRETAS

UNIVERSIDAD DE SAN BUENAVENTURA CALI
FACULTADDE INGENIERÍA
PROGRAMA DE INGENIERÍA DE SISTEMAS
SANTIAGO DE CALI 2010
GRAFOS PLANOS

Grafos

Los grafos son estructuras discretas que constan de vértices y de aristas que conectan entre siesos vértices. Hay varios tipos distintos de grafos, que se diferencian ente si por el tipo el número de aristas que pueden conectar cada par de vértices.
1. GRAFO SIMPLE: un grafo simple G=V,E consta de V, un conjunto no vacio de vértices, y de E, un conjunto de pares no ordenados de elementos distintos de V. A estos pares se les llama aristas.

2. MULTIGRAFO: un multígrafo G=(V,E)consta de V de vértices, un conjunto de Ede aristas y una función f de E en u,v | u,v∈ V, u≠v . Se dice que las aristas e1 y e2 son aristas múltiples o paralelas si f(e1)=f(e2) .


3. PSEUDOGRAFO: un pseudografo G=(V,E) consta de un conjunto E de aristasy una función f de E en u,v | u,v∈ V. Una arista e es un bucle, o lazo, si f=e=u,u={u} para algún u∈V.


4. GRAFODIRIGIDO: un grafo dirigido (V,E) consta de un conjunto de V de vértices y de un conjunto E de aristas, que son pares ordenados de elementos de V.


5. MULTIGRAFO DIRIGIDO: un multígrafo dirigido G=V,E consta de un conjunto V de vértices, un conjunto E de aristas y una función f de E en u,v | u,v∈ V.
Se dice que las aristas e1 y e2 son aristas múltiples si f(e1)=fe2.Terminología en teoría de grafos |
Tipos | Aristas | ¿Se admiten aristas múltiples? | ¿Se admiten bucles? |
Grafo simple Multígrafo Pseudografo Grafo dirigido Multígrafo dirigido | No dirigidas No dirigidas No dirigidas Dirigidas Dirigidas | No Si Si No Si | No No Si Si Si |

TERMINOLOGIA BASICA
* Dos vértices de un grafo no dirigido son Adyacentes(o vecinos)  si una arista los une.* Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
* El grado o valencia: el grado de un vértice de un grafo no dirigido es el número de aristas incidentes con él, exceptuando los bucles, cada uno contribuye con dos unidades al grado del vértice. El grado del vértice v se denota por δv.
Grado cero: a los de grado cero se les llaman aislados. Un vértice aislado noes adyacente a ningún vértice.
Grado uno: se dice que es un vértice colgante ó hoja, si y solo si, tiene grado uno.
Cada arista contribuye con dos unidades a la suma de los grados de los vértices, ya que cada arista es incidente con dos vértices (posiblemente iguales). Esto significa que los grados de los vértices es el doble del número de aristas.

FAMILIAS DISTINGUIDAS DE GRAFOS SIMPLESGrafos completos: un grafo completo es aquél donde todas sus aristas conectan cada par de vértices.

K1 | K2 | K3 | K4 |
K5 | K6 | K7 | K8 |

Grafo ciclo: o simplemente ciclo es un grafo que se asemeja a un poligono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclode n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes.

n-Cubos:   un cubo si sus vértices y aristas están relacionados como los de un cubo n-dimensional. Se denota por Qn al cubo asociado al cubo n-dimensional.

GRAFOS BIPARTITOS

Un grafo nodirigido cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro.

GRAFOS BIPARTITO COMPLETO
Es aquel Grafo bipartito en el que todos los vértices de la partición V1 están conectados a todos los vértices de la partición V2 y viceversa.

Representación de grafos.

Para empezar tenemos 2 formas de representar un grafo, la primera...