Çizge Teorisi (#1): Ağaçlar
Alıştırmalar
Aşağıdaki çizgelerden hangileri ağaçtır?
G = (V, E) ile V = \{a, b, c, d, e\} ve
E = \{ \{a, b\}, \{a, e\}, \{b, c\}, \{c, d\}, \{d, e\} \}G = (V, E) ile V = \{a, b, c, d, e\} ve
E = \{ \{a, b\}, \{b, c\}, \{c, d\}, \{d, e\} \}G = (V, E) ile V = \{a, b, c, d, e\} ve
E = \{ \{a, b\}, \{a, c\}, \{a, d\}, \{a, e\} \}G = (V, E) ile V = \{a, b, c, d, e\} ve E = \{ \{a, b\}, \{a, c\}, \{d, e\} \}
Aşağıdaki derece dizileri için, bunun her zaman bir ağacın derece dizisi olup olamayacağına, asla olamayacağına veya olabileceğine karar verin. Unutmayın, bir derece dizisi, bir çizgedeki tüm köşelerin derecelerini (köşeye bitişik kenar sayısı) artmayan sırayla listeler.
(4, 1, 1, 1, 1)
(3, 3, 2, 1, 1)
(2, 2, 2, 1, 1)
(4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1)
Aşağıdaki derece dizileri için, bunun her zaman bir ağacın derece dizisi olup olamayacağına, asla olamayacağına veya olabileceğine karar verin. Cevaplarınızı gerekçelendirin.
(3, 3, 2, 2, 2)
(3, 2, 2, 1, 1, 1)
(3, 3, 3, 1, 1, 1)
(4, 4, 1, 1, 1, 1, 1, 1)
Dikkatli olun: çizgeler bağlantılı olmayabilir.
- v köşe ve e kenara sahip bir çizgeniz olduğunu ve v = e + 1 koşulunu sağladığını varsayalım. Bu çizge bir ağaç olmak zorunda mıdır? Cevabınızı kanıtlayın.
İkinci alıştırmaya bakınız.
- v köşe ve e kenara sahip herhangi bir çizgenin (mutlaka bir ağaç olması gerekmez) v > e + 1 koşulunu sağlıyorsa, bağlantılı olmayacağını kanıtlayın.
Çelişkiyle kanıt yöntemini deneyin ve çizgenin bir kapsayan ağacını düşünün.
Eğer v köşe ve e kenara sahip bir G çizgesi bağlantılıysa ve v < e + 1 koşulunu sağlıyorsa, bir döngü içermek zorunda mıdır? Cevabınızı kanıtlayın.
Bir ormanı (forest), döngü içermeyen bir çizge olarak tanımlıyoruz.
Bunun neden iyi bir isim olduğunu açıklayın. Yani, bir ormanın neden ağaçların birleşimi olduğunu açıklayın.
F, m ağaç ve v köşeden oluşan bir orman olsun. F kaç kenara sahiptir? Açıklayın.
v köşe ve e kenara sahip herhangi bir G çizgesi v < e + 1 koşulunu sağlıyorsa, bir döngü içermek zorunda olduğunu (yani bir orman olamayacağını) kanıtlayın.
- kısmı için, bazı basit örnekler denemek size formülü verecektir. Daha sonra bunun doğru olduğunu kanıtlamanız yeterli olacaktır.
- Bir çizge, ancak ve ancak herhangi iki köşe arasında en fazla bir yol varsa bir ormandır. Her iki yön için de karşıt tersini kullanarak kanıt yapın (çelişkiyle kanıt değil).
Videoda kanıtını verdiğimiz önermenin kanıtını incelemek, ihtiyacınız olanın çoğunu size verecektir, ancak yalnızca ilgili kısımları verdiğinizden ve çelişkiyle kanıt kullanmadığınızdan emin olun.
- Her ağacın iki parçalı (bipartite) olduğunu minimal suçlu yöntemiyle dikkatlice kanıtlayın.
Burada minimalite, köşe sayısı açısından olmalıdır. Eğer bir minimal karşı örneğiniz varsa ve bir yaprak köşeyi çıkarırsanız, elde edilen çizge daha küçük bir ağaç olacaktır, bu yüzden…
Aşağıda çizilmiş olan ağacı düşünün.
e köşesini kök olarak belirlediğimizi varsayalım. Her köşenin çocuklarını, ebeveynlerini ve kardeşlerini listeleyin. e dışında herhangi bir köşenin torunu var mıdır?
e’nin kök olarak seçilmediğini varsayalım. Kök köşe seçimimiz, e’nin sahip olduğu çocuk sayısını değiştirir mi? Torun sayısını değiştirir mi? Her birinden kaç tane vardır?
Aslında, ağaçtaki herhangi bir köşeyi seçin ve bunun kök olmadığını varsayın. Bu köşenin çocuk sayısının, hangi köşenin kök olduğuna bağlı olmadığını açıklayın.
Önceki kısım diğer ağaçlar için de geçerli midir? Bunun geçerli olduğu farklı bir ağaç örneği verin. Ardından bunun her zaman geçerli olduğunu kanıtlayın veya geçerli olmadığı bir ağaç örneği verin.
Eğer e kök ise, b’nin üç çocuğu olacaktır (a, c ve d), bunların hepsi kardeştir ve ebeveynleri b’dir. a’nın hiç çocuğu olmayacaktır.
Genel olarak, bir köşe kök değilse, kaç çocuğa sahip olacağını nasıl belirleyebilirsiniz?
T, u, v ve w köşelerini (ve muhtemelen diğerlerini) içeren köklü bir ağaç olsun. Eğer w, hem u hem de v’nin soyu ise, o zaman u, v’nin soyudur veya v, u’nun soyudur. Bunu kanıtlayın.
Eğer zaten bir ağaç değilse, verilen bir G çizgesinin birden fazla kapsayan ağacı olacaktır. Bunlar ne kadar benzer veya farklı olmalıdır?
Verilen bir çizgenin tüm kapsayan ağaçları birbirine izomorfik olmak zorunda mıdır? Nedenini açıklayın veya bir karşı örnek verin.
Verilen bir çizgenin tüm kapsayan ağaçları aynı sayıda kenara sahip olmak zorunda mıdır? Nedenini açıklayın veya bir karşı örnek verin.
Bir çizgenin tüm kapsayan ağaçları aynı sayıda yaprağa (derecesi 1 olan köşelere) sahip olmak zorunda mıdır? Nedenini açıklayın veya bir karşı örnek verin.
Aşağıdaki çizgenin tüm kapsayan ağaçlarını bulun. Kaç farklı kapsayan ağaç vardır? İzomorfizm açısından kaç farklı kapsayan ağaç vardır (yani, tüm kapsayan ağaçları izomorfik olanlara göre gruplarsanız, kaç grup elde edersiniz)?
Tam olarak 7 farklı kapsayan ağaca sahip bir çizge örneği verin. Bu kapsayan ağaçların bazılarının veya tümünün izomorfik olması kabul edilebilir.
7 kenara sahip bir örnek vardır.
- Kendisi bir ağaç olmayan her bağlantılı çizgenin en az üç farklı (ancak izomorfik olabilir) kapsayan ağaca sahip olması gerektiğini kanıtlayın.
Önceki alıştırma yardımcı olacaktır.
- Bir çizgenin her kapsayan ağacında bulunması gereken kenarları düşünün. Her çizgenin böyle bir kenarı olmak zorunda mıdır? Tam olarak bir tane böyle kenara sahip bir çizge örneği verin.
Böyle bir kenar, eğer çıkarılırsa çizgeyi bağlantısız hale getirir. Bu tür bir kenara sahip çizgelere 1-bağlantılı (1-connected) denir.