Sin embargo, existen muchos tipos diferentes de gráficos según la cantidad de vértices, la cantidad de aristas, la interconectividad y su estructura general. Algunos de los tipos comunes de gráficos son los siguientes:
1. Gráfico nulo
A gráfico nulo es un gráfico en el que no hay aristas entre sus vértices. Un gráfico nulo también se llama gráfico vacío.
Ejemplo
Un gráfico nulo con n vértices se denota por Nn.
2. Gráfico trivial
A gráfico trivial es el grafo que tiene un solo vértice.
Ejemplo
En el gráfico anterior, solo hay un vértice 'v' sin ningún borde. Por tanto, es un gráfico trivial.
3. Gráfico sencillo
A grafico sencillo es el grafo no dirigido con sin bordes paralelos y sin bucles .
Un gráfico simple que tiene n vértices, el grado de cada vértice es como máximo n -1.Ejemplo
En el ejemplo anterior, el primer gráfico no es un gráfico simple porque tiene dos aristas entre los vértices A y B y también tiene un bucle.
El segundo gráfico es un gráfico simple porque no contiene ningún bucle ni aristas paralelas.
4. Gráfico no dirigido
Un gráfico no dirigido es un grafo cuyas aristas son no dirigido .
Ejemplo
En el gráfico anterior, dado que no hay aristas dirigidas, es un gráfico no dirigido.
5. Gráfico dirigido
A gráfico dirigido es un gráfico en el que los bordes están dirigidos por flechas.
El gráfico dirigido también se conoce como dígrafos .
Ejemplo
En el gráfico anterior, cada borde está dirigido por la flecha. Un borde dirigido tiene una flecha de A a B, significa que A está relacionado con B, pero B no está relacionado con A.
6. Gráfico completo
Un grafo en el que cada par de vértices está unido exactamente por una arista se llama grafico completo . Contiene todas las aristas posibles.
Un gráfico completo con n vértices contiene exactamente nC2 aristas y está representado por Kn.
Ejemplo
En el ejemplo anterior, dado que cada vértice del gráfico está conectado con todos los vértices restantes a través de exactamente un borde, ambos gráficos son gráficos completos.
7. Gráfico conectado
A gráfico conectado es un gráfico en el que podemos visitar desde cualquier vértice a cualquier otro vértice. En un gráfico conectado, existe al menos una arista o camino entre cada par de vértices.
Ejemplo
En el ejemplo anterior, podemos atravesar desde cualquier vértice a cualquier otro vértice. Significa que existe al menos un camino entre cada par de vértices, por lo tanto, es un gráfico conectado.
8. Gráfico desconectado
A gráfico desconectado es un gráfico en el que no existe ningún camino entre cada par de vértices.
Ejemplo
El gráfico anterior consta de dos componentes independientes que están desconectados. Dado que no es posible visitar desde los vértices de un componente a los vértices de otros componentes, es un gráfico desconectado.
9. Gráfico regular
A gráfico regular es un gráfico en el que el grado de todos los vértices es el mismo.
Si el grado de todos los vértices es k, entonces se llama gráfico k-regular.
Ejemplo
En el ejemplo anterior, todos los vértices tienen grado 2. Por lo tanto, se llaman 2- gráfico regular .
10. Gráfico cíclico
Un gráfico con 'n' vértices (donde, n>=3) y 'n' aristas formando un ciclo de 'n' con todas sus aristas se conoce como gráfico de ciclo .
Un gráfico que contiene al menos un ciclo se conoce como gráfico. gráfico cíclico .
En el gráfico de ciclo, el grado de cada vértice es 2.
El gráfico de ciclo que tiene n vértices se denota por Cn.
texto subrayado css
Ejemplo 1
En el ejemplo anterior, todos los vértices tienen grado 2. Por lo tanto, todos son gráficos cíclicos.
Ejemplo 2
Dado que el gráfico anterior contiene dos ciclos, es un gráfico cíclico.
11. Gráfico acíclico
Un gráfico que no contiene ningún ciclo se llama gráfico. gráfico acíclico .
Ejemplo
Dado que el gráfico anterior no contiene ningún ciclo, es un gráfico acíclico.
12. Gráfico bipartito
A gráfica bipartita es un gráfico en el que el conjunto de vértices se puede dividir en dos conjuntos de modo que los bordes solo vayan entre conjuntos, no dentro de ellos.
Un gráfico G (V, E) se llama gráfico bipartito si su conjunto de vértices V(G) se puede descomponer en dos subconjuntos disjuntos no vacíos V1(G) y V2(G) de tal manera que cada arista e ∈ E (G) tiene su última articulación en V1(G) y su último punto en V2(G).
La partición V = V1 ∪ V2 se conoce como bipartición de G.
Ejemplo 1
Ejemplo 2
13. Gráfico bipartito completo
A gráfico bipartito completo es un gráfico bipartito en el que cada vértice del primer conjunto está unido a cada vértice del segundo conjunto por exactamente una arista.
Un gráfico bipartito completo es un gráfico bipartito completo.
Complete Bipartite graph = Bipartite graph + Complete graph
Ejemplo
El gráfico anterior se conoce como K.4,3.
14. Gráfico estelar
Un gráfico en estrella es un gráfico bipartito completo en el que n-1 vértices tienen grado 1 y un solo vértice tiene grado (n -1). Esto se parece exactamente a una estrella donde (n - 1) vértices están conectados a un único vértice central.
Un gráfico estelar con n vértices se denota por Snorte.
Ejemplo
En el ejemplo anterior, de n vértices, todos los (n-1) vértices están conectados a un solo vértice. Por tanto, es un gráfico estelar.
15 Gráfico ponderado
Un gráfico ponderado es un gráfico cuyos bordes han sido etiquetados con algunos pesos o números.
La longitud de un camino en un gráfico ponderado es la suma de los pesos de todos los bordes del camino.
Ejemplo
En el gráfico anterior, si la ruta es a -> b -> c -> d -> e -> g entonces la longitud de la ruta es 5 + 4 + 5 + 6 + 5 = 25.
16. Multigráfico
Un gráfico en el que hay múltiples aristas entre cualquier par de vértices o hay aristas desde un vértice hacia sí mismo (bucle) se llama multigráfico .
Ejemplo
En el gráfico anterior, los conjuntos de vértices B y C están conectados con dos aristas. De manera similar, los conjuntos de vértices E y F están conectados con 3 aristas. Por tanto, es un gráfico múltiple.
17. Gráfico plano
A gráfico plano es una gráfica que podemos dibujar en un plano de tal manera que no hay dos aristas que se crucen excepto en un vértice en el que inciden.
Ejemplo
Es posible que el gráfico anterior no parezca plano porque tiene bordes que se cruzan. Pero podemos volver a dibujar el gráfico anterior.
Los tres dibujos planos del gráfico anterior son:
Los tres gráficos anteriores no constan de dos aristas que se cruzan y, por lo tanto, todos los gráficos anteriores son planos.
18. Gráfico no plano
Una gráfica que no es plana se llama gráfica no plana. En otras palabras, un gráfico que no se puede dibujar sin al menos un par de sus bordes cruzados se conoce como gráfico no plano.
Ejemplo
El gráfico anterior es un gráfico no plano.