Teoría de gráficos: tipos de gráficos
Hay varios tipos de gráficos según el número de vértices, el número de aristas, la interconectividad y su estructura general. En este capítulo analizaremos sólo algunos tipos importantes de gráficos.
Gráfico nulo
A graph having no edges se llama Gráfico nulo.
Ejemplo
En el gráfico anterior, hay tres vértices llamados 'a', 'b' y 'c', pero no hay aristas entre ellos. Por lo tanto, es un gráfico nulo.
Gráfico trivial
UNA graph with only one vertex se llama Gráfico Trivial.
Ejemplo
En el gráfico que se muestra arriba, solo hay un vértice 'a' sin otros bordes. Por lo tanto, es un gráfico trivial.
Gráfico no dirigido
Un gráfico no dirigido contiene bordes, pero los bordes no son dirigidos.
Ejemplo
En este gráfico, 'a', 'b', 'c', 'd', 'e', 'f', 'g' son los vértices y 'ab', 'bc', 'cd', 'da ',' ag ',' gf ',' ef 'son los bordes del gráfico. Dado que es un gráfico no dirigido, los bordes 'ab' y 'ba' son los mismos. Del mismo modo otros bordes también se consideran de la misma manera.
Gráfico dirigido
En un gráfico dirigido, cada borde tiene una dirección.
Ejemplo
En el gráfico anterior, tenemos siete vértices 'a', 'b', 'c', 'd', 'e', 'f' y 'g', y ocho aristas 'ab', 'cb', ' dc ',' ad ',' ec ',' fe ',' gf 'y' ga '. Como es un gráfico dirigido, cada borde tiene una marca de flecha que muestra su dirección. Tenga en cuenta que en un gráfico dirigido, 'ab' es diferente de 'ba'.
Gráfico simple
Un gráfico with no loops y no parallel edges se llama gráfico simple.
El número máximo de aristas posibles en un solo gráfico con 'n' vértices es n C 2 donde n C 2 = n (n - 1) / 2.
El número de gráficos simples posibles con 'n' vértices = 2 n c 2 = 2 n (n-1) / 2 .
Ejemplo
En el siguiente gráfico, hay 3 vértices con 3 aristas que es el máximo excluyendo las aristas paralelas y los bucles. Esto se puede demostrar utilizando las fórmulas anteriores.
El número máximo de aristas con n = 3 vértices -
El número máximo de gráficos simples con n = 3 vértices -
Estos 8 gráficos se muestran a continuación:
Gráfico conectado
Se dice que un gráfico G está conectado if there exists a path between every pair of vertices. Debe haber al menos una arista por cada vértice del gráfico. De modo que podemos decir que está conectado a algún otro vértice en el otro lado del borde.
Ejemplo
En el siguiente gráfico, cada vértice tiene su propia arista conectada a otra arista. Por lo tanto, es un gráfico conectado.
Gráfico desconectado
Un gráfico G está desconectado, si no contiene al menos dos vértices conectados.
Ejemplo 1
El siguiente gráfico es un ejemplo de un gráfico desconectado, donde hay dos componentes, uno con vértices 'a', 'b', 'c', 'd' y otro con 'e', 'f', 'g', vértices 'h'.
Los dos componentes son independientes y no están conectados entre sí. De ahí que se le llame gráfico desconectado.
Ejemplo 2
En este ejemplo, hay dos componentes independientes, abfe y cd, que no están conectados entre sí. Por tanto, este es un gráfico desconectado.
Gráfico regular
Se dice que una gráfica G es regular, if all its vertices have the same degree. En una gráfica, si el grado de cada vértice es 'k', entonces la gráfica se llama 'gráfica k-regular'.
Ejemplo
En las siguientes gráficas, todos los vértices tienen el mismo grado. Entonces, estos gráficos se llaman gráficos regulares.
En ambas gráficas, todos los vértices tienen grado 2. Se denominan Gráficas 2-Regulares.
Gráfico completo
Un gráfico simple con 'n' vértices mutuos se llama gráfico completo y es denoted by ‘Kn’. En el gráfico,a vertex should have edges with all other vertices, luego se llamó un gráfico completo.
En otras palabras, si un vértice está conectado a todos los demás vértices de un gráfico, entonces se llama gráfico completo.
Ejemplo
En los siguientes gráficos, cada vértice del gráfico está conectado con todos los vértices restantes del gráfico excepto por sí mismo.
En el gráfico I,
| un | segundo | C | |
|---|---|---|---|
| un | No conectado | Conectado | Conectado |
| segundo | Conectado | No conectado | Conectado |
| C | Conectado | Conectado | No conectado |
En el gráfico II,
| pags | q | r | s | |
|---|---|---|---|---|
| pags | No conectado | Conectado | Conectado | Conectado |
| q | Conectado | No conectado | Conectado | Conectado |
| r | Conectado | Conectado | No conectado | Conectado |
| s | Conectado | Conectado | Conectado | No conectado |
Gráfico de ciclo
Un gráfico simple con 'n' vértices (n> = 3) y 'n' aristas se denomina gráfico cíclico si todos sus aristas forman un ciclo de longitud 'n'.
Si el grado de cada vértice en el gráfico es dos, entonces se llama Gráfico de ciclo.
Notation- C n
Ejemplo
Eche un vistazo a los siguientes gráficos:
El gráfico I tiene 3 vértices con 3 aristas que forman un ciclo 'ab-bc-ca'.
El gráfico II tiene 4 vértices con 4 aristas que forman un ciclo 'pq-qs-sr-rp'.
El gráfico III tiene 5 vértices con 5 aristas que forman un ciclo 'ik-km-ml-lj-ji'.
Por tanto, todos los gráficos dados son gráficos de ciclos.
Gráfico de rueda
Un gráfico de rueda se obtiene a partir de un gráfico de ciclo C n-1 agregando un nuevo vértice. Ese nuevo vértice se llamaHubque está conectado a todos los vértices de C n .
Notación - W n
Núm. De aristas en W n = Núm. De aristas desde el centro a todos los demás vértices +
No. de aristas de todos los demás nodos en el gráfico de ciclo sin un concentrador.
= (n – 1) + (n – 1)
= 2 (n – 1)
Ejemplo
Eche un vistazo a los siguientes gráficos. Todos son gráficos de rueda.
En el gráfico I, se obtiene de C 3 agregando un vértice en el medio llamado 'd'. Se denota como W 4 .
Número de aristas en W4 = 2 (n-1) = 2 (3) = 6
En el gráfico II, se obtiene de C4 agregando un vértice en el medio llamado 't'. Se denota como W 5 .
Número de aristas en W5 = 2 (n-1) = 2 (4) = 8
En el gráfico III, se obtiene de C 6 agregando un vértice en el medio llamado 'o'. Se denota como W 7 .
Número de aristas en W4 = 2 (n-1) = 2 (6) = 12
Gráfico cíclico
Un gráfico with at least one ciclo se llama gráfico cíclico.
Ejemplo
En el gráfico de ejemplo anterior, tenemos dos ciclos abcda y cfgec. Por eso se llama gráfico cíclico.
Gráfico acíclico
Un gráfico with no cycles se llama gráfico acíclico.
Ejemplo
En el gráfico de ejemplo anterior, no tenemos ningún ciclo. Por tanto, es un gráfico no cíclico.
Gráfica bipartita
Un gráfico simple G = (V, E) con partición de vértice V = {V 1 , V 2 } se llama gráfico bipartitoif every edge of E joins a vertex in V1 to a vertex in V2.
En general, un gráfico Bipertite tiene dos conjuntos de vértices, digamos, V1 y V2, y si se dibuja una arista, debe conectar cualquier vértice del conjunto V 1 a cualquier vértice del conjunto V 2 .
Ejemplo
En este gráfico, puede observar dos conjuntos de vértices: V 1 y V 2 . Aquí, dos aristas llamadas 'ae' y 'bd' conectan los vértices de dos conjuntos V 1 y V 2 .
Gráfico bipartito completo
Un gráfico bipartito 'G', G = (V, E) con partición V = {V 1 , V 2 } se dice que es un gráfico bipartito completo si cada vértice de V 1 está conectado a cada vértice de V 2 .
En general, un gráfico bipartito completo conecta cada vértice del conjunto V 1 a cada vértice del conjunto V 2 .
Ejemplo
El siguiente gráfico es un gráfico bipartito completo porque tiene aristas que conectan cada vértice del conjunto V 1 con cada vértice del conjunto V 2 .
Si | V 1 | = my | V 2 | = n, entonces el gráfico bipartito completo se denota por K m, n .
- K m, n tiene (m + n) vértices y (mn) aristas.
- K m, n es una gráfica regular si m = n.
En general, un complete bipartite graph is not a complete graph.
K m, n es un gráfico completo si m = n = 1.
El número máximo de aristas en un gráfico bipartito con n vértices es -
[n 2 /4]
Si n = 10, k5, 5 = [n2 / 4] = [10 2 /4] = 25.
Del mismo modo, K6, 4 = 24
K7, 3 = 21
K8, 2 = 16
K9, 1 = 9
Si n = 9, k5, 4 = [n2 / 4] = [92/4] = 20
Del mismo modo, K6, 3 = 18
K7, 2 = 14
K8, 1 = 8
'G' es un gráfico bipartito si 'G' no tiene ciclos de longitud impar. Un caso especial de gráfico bipartito es un gráfico de estrella.
Gráfico de estrella
Un gráfico bipartito completo de la forma K1, n-1 es un gráfico en estrella con n vértices. Un gráfico en estrella es un gráfico bipartito completo si un solo vértice pertenece a un conjunto y todos los vértices restantes pertenecen al otro conjunto.
Ejemplo
En los gráficos anteriores, de 'n' vértices, todos los vértices 'n – 1' están conectados a un solo vértice. Por lo tanto, tiene la forma de K 1 , n-1, que son gráficos en estrella.
Complemento de un gráfico
Sea 'G−' un gráfico simple con algunos vértices como el de 'G' y una arista {U, V} está presente en 'G−', si la arista no está presente en G. Significa que dos vértices son adyacentes en 'G−' si los dos vértices no son adyacentes en G.
Si los bordes que existen en el gráfico I están ausentes en otro gráfico II, y si tanto el gráfico I como el gráfico II se combinan para formar un gráfico completo, entonces el gráfico I y el gráfico II se denominan complementarios entre sí.
Ejemplo
En el siguiente ejemplo, graph-I tiene dos aristas 'cd' y 'bd'. Su complemento Graph-II tiene cuatro aristas.
Tenga en cuenta que las aristas en el gráfico I no están presentes en el gráfico II y viceversa. Por lo tanto, la combinación de ambos gráficos da un gráfico completo de 'n' vértices.
Note - Una combinación de dos gráficos complementarios da un gráfico completo.
Si 'G' es un gráfico simple, entonces
| E (G) | + | E ('G -') | = | E (Kn) |, donde n = número de vértices en el gráfico.
Ejemplo
Sea 'G' una gráfica simple con nueve vértices y doce aristas, encuentre el número de aristas en 'G-'.
Tienes, | E (G) | + | E ('G -') | = | E (Kn) |
12 + | E ('G -') | =
9 (9-1) / 2 = 9 C 2
12 + | E ('G -') | = 36
| E ('G -') | = 24
'G' es un gráfico simple con 40 aristas y su complemento 'G−' tiene 38 aristas. Encuentra el número de vértices en la gráfica G o 'G−'.
Deje que el número de vértices en la gráfica sea 'n'.
Tenemos, | E (G) | + | E ('G -') | = | E (Kn) |
40 + 38 = n (n-1) / 2
156 = n (n-1)
13 (12) = n (n-1)
n = 13