logo

Ağaç ve Orman

1. Ağaç ve Orman Nedir?

Ağaç

  • Grafik teorisinde, bir ağaç bir yönlendirilmemiş, bağlantılı ve döngüsel olmayan grafik . Başka bir deyişle, tek bir döngüyü bile içermeyen bağlantılı bir grafa ağaç denir.
  • Bir ağaç, hiyerarşik yapıyı grafiksel biçimde temsil eder.
  • Ağacın elemanlarına düğümleri, kenarlarına ise dallar denir.
  • N köşeli bir ağacın (n-1) kenarı vardır.
  • Ağaçlar, bilgisayar biliminin veri yapılarında aile ağacı kadar basit, ağaçlar kadar karmaşık birçok yararlı uygulama sağlar.
  • A yaprak Bir ağaçta derece 1 olan bir köşe bulunur veya çocuğu olmayan herhangi bir köşeye yaprak denir.

Örnek

Ağaç ve Orman

Yukarıdaki örnekte hepsi 6'dan az köşeye sahip ağaçlardır.

Orman

Grafik teorisinde, bir orman dır-dir yönlendirilmemiş, bağlantısız, döngüsel olmayan bir grafik . Başka bir deyişle, birbirinden ayrı ağaç topluluğu orman olarak bilinir. Bir ormanın her bileşeni ağaçtır.

Örnek

Ağaç ve Orman

Yukarıdaki grafik iki alt grafik gibi görünse de birbiriyle bağlantısız tek bir grafiktir. Yukarıdaki grafikte herhangi bir döngü yoktur. Bu nedenle ormandır.


2. Ağaçların Özellikleri

  1. En az iki köşesi olan her ağacın en az iki yaprağı olmalıdır.
  2. Ağaçların birçok özelliği vardır:
    T, n köşeli bir grafik olsun, o zaman aşağıdaki ifadeler eşdeğerdir:
    • T bir ağaçtır.
    • T hiçbir döngü içermez ve n-1 kenara sahiptir.
    • T bağlantılıdır ve (n-1) kenarına sahiptir.
    • T bağlantılı grafiktir ve her kenar bir kesme kenarıdır.
    • T grafiğinin herhangi iki köşesi tam olarak bir yolla bağlanır.
    • T hiçbir döngü içermez ve herhangi bir yeni e kenarı için T+ e grafiğinin tam olarak bir döngüsü vardır.
  3. Bir ağacın her kenarı kesilmiştir.
  4. Bir ağaca bir kenar eklemek tam olarak bir döngüyü tanımlar.
  5. Her bağlı grafik bir kapsayan ağaç içerir.
  6. Her ağacın ikinci dereceden en az iki köşesi vardır.

3. Yayılan Ağaç

A kapsayan ağaç bağlantılı bir grafikte G, G'nin tüm köşelerini içeren ve aynı zamanda bir ağaç olan G'nin bir H alt grafiğidir.

Örnek

Aşağıdaki G grafiğini düşünün:

Ağaç ve Orman

Yukarıdaki G grafiğinden aşağıdaki üç yayılan ağacı (H) uygulayabiliriz:

Ağaç ve Orman

Yayılan Ağacı bulma yöntemleri

Yayılan ağacı iki yöntemden birini kullanarak sistematik olarak bulabiliriz:

  1. Kesme Yöntemi
  2. Oluşturma Yöntemi

1. Kesme yöntemi

  • Grafik G'de herhangi bir döngüyü seçmeye başlayın.
  • Döngünün kenarlarından birini çıkarın.
  • Hiçbir döngü kalmayana kadar bu işlemi tekrarlayın.

Örnek

  • Bir G grafiği düşünün,
Ağaç ve Orman
  • Yukarıdaki grafikte a-d-c-a döngüsünü yok eden ac kenarını kaldırırsak aşağıdaki grafiği elde ederiz:
Ağaç ve Orman
  • Yukarıdaki grafikten a-d-c-b-a döngüsünü yok eden cb kenarını çıkarırsak aşağıdaki grafiği elde ederiz:
Ağaç ve Orman
  • Yukarıdaki grafikten d-e-c-d döngüsünü yok eden ec kenarını kaldırırsak aşağıdaki yayılma ağacını elde ederiz:
Ağaç ve Orman

2. Oluşturma yöntemi

  • G grafiğinin kenarlarını birer birer seçin. Hiçbir döngü oluşturulmayacak şekilde.
  • Tüm köşeler dahil edilene kadar bu işlemi tekrarlayın.

Örnek

Aşağıdaki G grafiğini düşünün,

Ağaç ve Orman
  • Kenarı seçin ab ,
Ağaç ve Orman
  • Kenarı seçin ile ilgili ,
Ağaç ve Orman
  • Bundan sonra kenarı seçin ak ,
Ağaç ve Orman
  • Ardından kenarı seçin cb , sonunda aşağıdaki kapsayan ağacı elde ederiz:
Ağaç ve Orman

Devre Sıralaması

Yayılan bir ağaç elde etmek için G'den silmemiz gereken kenar sayısı.

Yayılan ağaç G = m- (n-1) , buna denir devre sıralaması G.'nin

 Where, m = No. of edges. n = No. of vertices. 

Örnek

Ağaç ve Orman

Yukarıdaki grafikte kenarlar m = 7 ve köşeler n = 5

O halde devre sıralaması,

 G = m - (n - 1) = 7 - (5 - 1) = 3