Tipos de Grafos CYD
Tipos de Grafos CYD
Tipos de Grafos CYD
Otra definicin es que es un grafo no dirigido de tal modo que para cualquier par de nodos
existe al menos un camino que los une.
Un grafo no dirigido es conexo si existe un camino entre cualquier par de nodos que forman
el grafo. Ejemplo:
Un grafo es doblemente conexo si para cada par de vrtices est conectado por al menos
dos caminos disjuntos, es decir, se dice que es conexo y no existe un vrtice tal que al
sacarlo el grafo resultante sea disconexo.
Tema opcional: Un grafo es completo si existen aristas uniendo todos los pares posibles de
vrtices, es decir, si para todo par de vrtices (a, b) debe tener una arista e que los une.
Existe tambin llamado Grafo fuertemente conexo que es un grafo dirigido tal que para
cualquier par de nodos existe un camino que los une.
1
Un digrafo es fuertemente conexo si cualquier par de vrtices se puede unir por un
camino dirigido.
GRAFOS BIPARTIDOS
2
Definicin 1
Un grafo no dirigido es bipartito si sus vrtices pueden repartirse en dos conjuntos disjuntos
de tal forma que todas las aristas tengan un extremo en cada uno de esos conjuntos.
Dicho de otra forma, un grafo es bipartito si sus vrtices pueden colorearse utilizando dos
colores de tal forma que no exista ninguna arista que conecte dos vrtices del mismo color.
De los dos grafos no dirigidos siguientes, el de la izquierda es bipartito, pero el de la
derecha no lo es.
Son aquellos grafos que se pueden colorear en dos colores grafos bipartitos
Definicin: Sea G=(V,A). Se dice que G es bipartito si existen V1, V2 tales que:
1. V1 V2= V
2. V1 V2=
3. Para toda {vi,vj} A se cumple vi V1, vj V2
3
Idea de cmo pintarlo:
Definicin 2
4
A continuacin, mostramos dos ejemplos de grafos bipartidos donde /V1(G)/ = 3 y
/V2(G)/= 4
.
Un grafo bipartido en el cual todos los elementos de V1 estn unidos con todos los
elementos de V2 se denomina grafo bipartido completo.
Teorema 1.3
Un grafo no dirigido es bipartido si no contiene ningn ciclo impar.
Fuente: http://teoriadegrafos.blogspot.com.co/2007/03/grafos-bipartidos.html