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
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
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
- En az iki köşesi olan her ağacın en az iki yaprağı olmalıdır.
- 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.
- Bir ağacın her kenarı kesilmiştir.
- Bir ağaca bir kenar eklemek tam olarak bir döngüyü tanımlar.
- Her bağlı grafik bir kapsayan ağaç içerir.
- 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:
Yukarıdaki G grafiğinden aşağıdaki üç yayılan ağacı (H) uygulayabiliriz:
Yayılan Ağacı bulma yöntemleri
Yayılan ağacı iki yöntemden birini kullanarak sistematik olarak bulabiliriz:
- Kesme Yöntemi
- 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,
- 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:
- 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:
- 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:
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,
- Kenarı seçin ab ,
- Kenarı seçin ile ilgili ,
- Bundan sonra kenarı seçin ak ,
- Ardından kenarı seçin cb , sonunda aşağıdaki kapsayan ağacı elde ederiz:
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
Yukarıdaki grafikte kenarlar m = 7 ve köşeler n = 5
O halde devre sıralaması,
G = m - (n - 1) = 7 - (5 - 1) = 3