Tipos De Grafos
Grafos simples.- Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto esequivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multigrafo.
Grafo completo.- Un grafo es completo si existen aristasuniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn elgrafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2 aristas.
La representación gráfica de los como los vértices de un polígono regular da cuenta desu peculiar estructura.
Grafos bipartitos.- Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientescondiciones:
V1 y V2 son disjuntos y no vacíos.
Cada arista de A une un vértice de V1 con uno de V2.
No existen aristas uniendo dos elementos de V1; análogamente para V2.
Bajo estas condiciones, elgrafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los quedebe unirse un elemento de la columna A con un elemento de la columna B.
Grafos Planos.- Un grafo G es planar si admite una representación en el plano de tal forma que las aristas no se cortan,salvo en sus extremos. A dicha representación se le denomina grafo plano. Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo sele llama representación plana del grafo.
Grafo planar
Grafo conexo.- Un grafo se dice que es conexo si cada par de sus vértices están conectados. Es decir,
G es conexo ⇐⇒∀u, v : ∃µ = [u,...
Regístrate para leer el documento completo.