Teoría de grafos - Ejemplos

En este capítulo, cubriremos algunos ejemplos estándar para demostrar los conceptos que ya discutimos en los capítulos anteriores.

Ejemplo 1

Find the number of spanning trees in the following graph.

Solución

El número de árboles de expansión obtenidos del gráfico anterior es 3. Son los siguientes:

Estos tres son los árboles de expansión para los gráficos dados. Aquí los gráficos I y II son isomorfos entre sí. Claramente, el número de árboles de expansión no isomorfos es dos.

Ejemplo 2

How many simple non-isomorphic graphs are possible with 3 vertices?

Solución

Hay 4 grafos no isomorfos posibles con 3 vértices. Se muestran a continuación.

Ejemplo 3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

Solución

Por el teorema de la suma de grados,

20 Σ i = 1 grado (Vi) = 2 | E |

20 (3) = 2 | E |

| E | = 30

Por la fórmula de Euler,

| V | + | R | = | E | + 2

20+ | R | = 30 + 2

| R | = 12

Por tanto, el número de regiones es 12.

Ejemplo 4

What is the chromatic number of complete graph Kn?

Solución

En una gráfica completa, cada vértice es adyacente a los vértices restantes (n – 1). Por tanto, cada vértice requiere un nuevo color. De ahí el número cromático K n = n.

Ejemplo 5

What is the matching number for the following graph?

Solución

Número de vértices = 9

Podemos unir solo 8 vértices.

El número coincidente es 4.

Ejemplo 6

What is the line covering number of for the following graph?

Solución

Número de vértices = | V | = n = 7

Número de cobertura de línea = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

Usando 3 aristas, podemos cubrir todos los vértices.

Por lo tanto, el número que cubre la línea es 3.