Çizge Teorisi - Örnekler

Bu bölümde, daha önceki bölümlerde tartıştığımız kavramları göstermek için birkaç standart örneği ele alacağız.

örnek 1

Find the number of spanning trees in the following graph.

Çözüm

Yukarıdaki grafikten elde edilen yayılan ağaç sayısı 3'tür. Bunlar aşağıdaki gibidir -

Bu üç, verilen grafikler için uzanan ağaçlardır. Burada I ve II grafikleri birbirine izomorftur. Açıkça, izomorfik olmayan yayılan ağaçların sayısı ikidir.

Örnek 2

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

Çözüm

3 köşeli 4 izomorfik olmayan grafik mümkündür. Aşağıda gösterilmiştir.

Örnek 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.

Çözüm

Derece teoreminin toplamına göre,

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

20 (3) = 2 | E |

| E | = 30

Euler'in formülüne göre,

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

20+ | R | = 30 + 2

| R | = 12

Dolayısıyla bölge sayısı 12'dir.

Örnek 4

What is the chromatic number of complete graph Kn?

Çözüm

Tam bir grafikte, her köşe, kalan (n – 1) köşelere bitişiktir. Bu nedenle, her köşe için yeni bir renk gerekir. Dolayısıyla kromatik sayı K n = n.

Örnek 5

What is the matching number for the following graph?

Çözüm

Köşe sayısı = 9

Yalnızca 8 köşeyi eşleştirebiliriz.

Eşleşen numara 4'tür.

Örnek 6

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

Çözüm

Köşe sayısı = | V | = n = 7

Satır kaplama sayısı = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

3 kenar kullanarak tüm köşeleri kapatabiliriz.

Dolayısıyla satır kaplama numarası 3'tür.