Teoria grafów - przykłady

W tym rozdziale omówimy kilka standardowych przykładów, aby zademonstrować koncepcje, które omówiliśmy już we wcześniejszych rozdziałach.

Przykład 1

Find the number of spanning trees in the following graph.

Rozwiązanie

Liczba drzew rozpinających uzyskana z powyższego wykresu wynosi 3. Są one następujące -

Te trzy są drzewami rozpinającymi dla danych wykresów. Tutaj wykresy I i II są względem siebie izomorficzne. Oczywiście liczba nieizomorficznych drzew rozpinających wynosi dwa.

Przykład 2

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

Rozwiązanie

Możliwe są 4 nieizomorficzne grafy z 3 wierzchołkami. Przedstawiono je poniżej.

Przykład 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.

Rozwiązanie

Twierdzenie o sumie stopni

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

20 (3) = 2 | E |

| E | = 30

Według wzoru Eulera,

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

20+ | R | = 30 + 2

| R | = 12

Stąd liczba regionów wynosi 12.

Przykład 4

What is the chromatic number of complete graph Kn?

Rozwiązanie

Na pełnym wykresie każdy wierzchołek sąsiaduje z pozostałymi (n – 1) wierzchołkami. Dlatego każdy wierzchołek wymaga nowego koloru. Stąd liczba chromatyczna K n = n.

Przykład 5

What is the matching number for the following graph?

Rozwiązanie

Liczba wierzchołków = 9

Możemy dopasować tylko 8 wierzchołków.

Pasująca liczba to 4.

Przykład 6

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

Rozwiązanie

Liczba wierzchołków = | V | = n = 7

Numer pokrycia linii = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

Używając 3 krawędzi, możemy pokryć wszystkie wierzchołki.

Stąd numer obejmujący linię to 3.