Estructura de datos

¿Grafo Perfecto?

Es un grafo en el que el numero cromatico de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.
En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos.

¿Grafo Rueda?

es un grafo con n vertices que se forma conectando un único vértice a todos los vértices de un cliclo(n-1). Los grafos rueda son grafos planos, y como tales pueden ser "incrustado" en un plano. Más específicamente, todo gráfico rueda es un grafo de Halin. Son auto-duales: el dual de cualquier grafo rueda es un grafo.

¿Grafo plano?

Es un grafo que puede ser dibujado en el plano sin que ninguna aristase cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K₅ y el K_3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.
Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de generoarbitrario. En esta terminología, los grafos planos tienen genero 0, por ser el plano y la esfera de género 0.

¿Grafo Bipartito Completo?

Es un grafo bipartito tal que

\forall v_1 \in V_1, \forall\ v_2 \in V_2 \Rightarrow e(v_1, v_2) \in E.\,

Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.
El grafo completo bipartito con particiones de tamaño

\left|V_1\right|=m

\left|V_2\right|=n,

es denotado como

K_{m,n}\,

¿Grafo BiPartito ?

Se denomina al grafo cuyos vértices se pueden separar en dos subconjuntos disjuntos V1(G) y V2(G) y las líneas siempre unen vértices de un subconjunto con vértices de otro subconjunto. Además se tiene que:

V1(G) U V2(G) = V(G).
La intersección de V1(G) y V2(G) es vacío.
Para todos los puntos x1, x2 en V1(G) y para todos los puntos y1, y2 en V2(G) , no existe línea alguna x = (x1,x2) , ni x = (y1,y2).

A continuación, 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 están unidos con todos los elementos de V2 se denomina grafo bipartido completo.

El conjunto de los grafos bipartidos completos es denominado con la letra K. En particular, un grafo completo bipartido que une dos conjuntos, de m y n elementos respectivamente, se denota por Km,n. Es obvio que Km,n tiene p=(m+n) vértices y q=mn líneas.