Teoria dei grafi - Esempi

In questo capitolo tratteremo alcuni esempi standard per dimostrare i concetti che abbiamo già discusso nei capitoli precedenti.

Esempio 1

Find the number of spanning trees in the following graph.

Soluzione

Il numero di spanning tree ottenuto dal grafico sopra è 3. Sono i seguenti:

Questi tre sono gli spanning tree per i grafici dati. Qui i grafici I e II sono isomorfi tra loro. Chiaramente, il numero di spanning tree non isomorfi è due.

Esempio 2

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

Soluzione

Sono possibili 4 grafici non isomorfi con 3 vertici. Sono mostrati di seguito.

Esempio 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.

Soluzione

Dalla somma dei gradi teorema,

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

20 (3) = 2 | E |

| E | = 30

Secondo la formula di Eulero,

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

20+ | R | = 30 + 2

| R | = 12

Quindi, il numero di regioni è 12.

Esempio 4

What is the chromatic number of complete graph K_n?

Soluzione

In un grafo completo, ogni vertice è adiacente ai rimanenti (n – 1) vertici. Quindi, ogni vertice richiede un nuovo colore. Da qui il numero cromatico K _n = n.

Esempio 5

What is the matching number for the following graph?

Soluzione

Numero di vertici = 9

Possiamo abbinare solo 8 vertici.

Il numero corrispondente è 4.

Esempio 6

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

Soluzione

Numero di vertici = | V | = n = 7

Numero di copertura della linea = (α ₁ ) ≥ [n / 2] = 3

α ₁ ≥ 3

Usando 3 bordi, possiamo coprire tutti i vertici.

Quindi, il numero di copertura della linea è 3.