ÇİZGE KURAMININ TEMELLERİ

ÜDK : 513.83

Çizge Kuramının Temelleri 1

Yurdakul CEYHUN ODTÜ

ÖZET

Bu yazıda çizge kuramının temel kavramları ve ilişkin dokusal denklemler tanımlanmıştır.

SUMMARY

Fundamental concepts of graph theory and the related topological equations are presented.

1. GİRİŞ

Devre çözümlemesinde karşılaşılan başlıca so runlardan biri de, devreyi oluşturan öğelerin aralarındaki bağlantının, başka bir deyişle dev renin dokusunun, matematiksel olarak tanım lanmasıdır. Çizge kuramı bu konuda büyük ko laylıklar sağlamaktadır. Biz bu yazı dizisinde çizge kuramının temel kavramlarını vererek, bunların devre çözümlemesindeki uygulamasını göstereceğiz.

Euler (1707 1782) ünlü Königsberg Köprüsü so rununa çözüm ararken çizge kuramının temel lerini atanlardan biri olmuştu. Königsberg ken tinden akan Pregel ırmağındaki iki ada birbir lerine ve kıyılarına Şekil 1.1 de gösterildiği gibi yedi köprü ile bağlanmıştı. Euler'i düşündüren

köprüden de yalnızca birer kez geçerek yine ilk başlama yerine geri dönmenin olanaklı olup olmadığı idi. Bu ve buna benzer ilginç bulma caların çözümlerini ararken matematikçiler gi derek değişik tür bir matematiğin gelişmesine yol açtılar.

Yakın zamana kadar pek uygulama olanağı bu lunmayan çizge kuramı, bilgisayara dayanan ye ni yöntemlerin gelişmesi ile elektrik mühen disliğinden yöneylem araştırmasına kadar ge niş bir alanı kapsayan çalışmalarda aranan bir matematik kolu oldu. örneğin, bir ülkenin de miryolu ağını düşünelim. Diyelim ki bu ülke de 6 demiryolu durağı olsun ve bu duraklar birbirlerine Şekil 1.2 de gösterildiği gibi bağ lansınlar. Şekil 1.2 deki çizgiler ve noktalar sırasıyla bu demiryolu ağının demiryollarını ve duraklarını simgesel olarak göstermektedir.

Şekil 1.1.

sorun A, B, C ya da D ile gösterilen herhangi bir yerden başlıyarak uçmadan, yüzmeden ya da yerkürenin çevresinde dolanmadan bu yedi

Şekil 12.

Başka bir deyişle Şekil 1.2 bu demiryolu ağı nın çizgesidir. Bu çizgenin ilginç bir yanı şu dur : buradaki her bir çizgi ve noktanın so mut karşıtları vardır. Çizgiler demiryollarına, noktalar da duraklara karşıt oluyorlar. Oysa,

böyle bir somut karşıtlık, çizge kuramında ara nan bir koşul değildir. Başka bir örnek olarak, şöyle bi: arkadaşlık ilişkisi düşünelim: A: B nin; B : A ve C nııı, C : B, D, E ve F nin, D : C ve E nııı, E C, D ve F nm; F ise C ve E nin arkadaşı olsunlar. Şekil 1.2, kolaylıkla görülece ği gibi bu arkadaşlık ilişkilerinin çizgesı ola rak da düşünülebilir. Bu örnekte artık çizgi ler somut kavramlara karşıt değildirler.

Bu tür daha başka örneklere girmeden çizge kuramının temel kavramlarını verelim.

2. ÇIZGE KURAMININ TEMEL KAVRAMLA RI

Şimdi, ilerde yazacaklarımızın açıklık kazana bilmesi için aşağıdaki tanımları verelim.

Tanım 2.1.

«Çizgi», iki ayrı uç noktası olan bir doğru par çasıdır.

Tanım 22.

Bir çizginin her bir uç noktasına «düğüm» de nir.

Şekil 2.1 de eo çizgisi ve v,, v2 ile tanımlanan düğümleri gösterilmiştir. Bu iki tanımdan an laşılmalıdır ki, bir çizginin yalnızca kendisi ve düğümleri tanımlanmaktadır, dolayısıyle bu çizginin yönünden, uzunluğundan vb. söz edi lemez.

olabilir. Diğer bir durum ise bir çizgi bir dü ğüme iki kez çakışabilir, böyle bir çizgiye «tek çevre» diyoruz. Tekçevreler, bir çizginin uç dü ğümlerinin çakışmasında doğar. Şekil 2 2a ve 2.2b de tekdüğüm ve tekçevre gösterilmiştir Yi ne Tanım 2 4 den varılacak bir sonuç, bir çiz (a)

Şekil 22.

gedekı çizgilerin düğümlerden başka ortak ke sişme noktalarının olamıyacağıdır. Şekil 2 3a ve 2 3b de düğümlerden başka ortak noktaları var gibi gözüken çizgeler, ve Şekil 2.3c ve 2.3d de ise bu çizgelerin yeniden çizilişleri göste rilmiştir. Bundan böyle e bir çizgedeki çizgi

Şekil 2.1.

Tanım 2.3. Eğer \ı düğümü e, çizgisinin düğümlerinden birisi ise v, düğümü ve e, çizgisi «çakışıktır» denir.

Demek ki \ı düğümü ile e( çizgisinin çakışık olmaması, v, nin e, nin iki uç düğümlerinden birisi olmadığı anlamına gelir.

Tanım 2.4. Rasgele sayıda çizgilerin düğümlere çakışık olduğu çizgiler ve düğümler kümesinin tümü ne «çizge» denir. Şimdi Tanım 2.4 den bir G çizgesinin içerdiği ve içermediği durumlan inceliyelim. G nin için de hiçbir çizginin çakışmıyacağı tekdüğümler

(d)

Şekil 23.

ve v ise düğüm sayısını göstersin. Şekil 2.4 de e = 7 ve v = 5 olan G çizgesi gösterilmiştir.

Şekil 2.4.

G çizgesinden e, çizgisinin çıkartılması ile el de edilen G, çizgesini düşünelim.

G, = G

(2.1)

Gj ve ej Şekil 2.5 de gösterilmiştir. Burada açık lanması gereken diğer bir nokta da, e: çizgisi G çizgesinden çıkartılırken vı ve v2 düğümleri

nin davranışlarıdır. Yukarda tekdüğümlerden söz edildiyse de tekçizgi (uç düğümleri olmı yan çizgi) gibi bir tanım verilmedi. Dolayısıyle böyle bir çıkartma işleminde G çizgesinde tek olan Vj ve v2 düğümleri Şekil 2.5 de ikiye ayrıl maktadır. Bu işlemin tersini, ej in G, ile «bir leşimini» düşünelim.

G = e,

(22)

Burada ise, Şekil 2.5 de herbiri iki ayrı düğüm olarak gösterilen v, ve v2 birleşerek herbiri bi rer düğümle gösterilmektedir. Varılacak sonuç şudur: tekdüğüm olmadıkça, bir çizgeden bir düğüm çıkartılamaz ve böyle bir işlem tanım lanamaz.

Tanım 2.5.

G çizgesinin çizgilerinin ve/ya da tekdüğümle rinin altkümesinden oluşan Gs çizgesine, G nin «altçizgesi» denir.

GB c G

(2.3)

Dolayısıyle yukardaki örnekle sözü edilen ej çizgisi, G nin bir altçizgesidir.

e, c G ya da G, e, in «üstçizgesidir».

G > e.

(2.4) (2.5)

Kolayca anlaşılacağı gibi Gs in tek bir çizgiden oluşması gibi bir koşul yoktur. Şekil 2.5 deki G çizgesini,

j = (e,,e3)e5)

(2.6)

altçizgesini düşünelim G den G, in çıkartılması ile elde edilecek altçizge G2 olsun,

G2 = G — Gj O zaman,

(2.7)

G2 = (e2,e4,e6,e,)

(2.8)

çizgilerinden oluşur. Böyle tanımlanan G2 alt çizgesine, G, in «tümleyeni» denir. Gı ve G2 nin özelliklerinden ikisi, bileşimlerinin G ye eşit:

G = G,

(2.9)

ve kesişimlerinin de «boşçizge» olmasıdır:

G2 = O

(2.10)

Bozçizge, ne bir çizgisi ne de bir düğümü olan çizgedir. Her nekadar burada denklem 2.10 daki boşçizgeden herhangi bir çizge gibi, söz ediliyorsa da, ilerde açıklanacağı gibi bu, tam anlamı ile bir çizge değildir ve bir çeliş kiye düşmemek için boşçizge kullanılırken dik kat etmek gerekmektedir, öyle ise tümleralt çizgenin tanımını verelim.

Tanım 2.6.

G, ve G2, G çizgesinin iki altçizgesi olsunlar. Eğer,

G, U G2 = G

Gt n G2 = 0 ise Gj ve G2 birbirlerine göre G nin «tümler altçizgeleridir».

Özel durumda, Gj = G ise G2 boşçizge olur, ve Gj, G2 yine Tanım 2.6 yi sağlarlar. Her çizge için böyle bir durumdan söz edilebilir. Demek oluyor ki her çizge kendi kendisinin bir alt çizgesidir. Bu özel durumun dışında Gj ^s G olacaktır. Bir altçizge verilen çizgeye özdeş de ğil ise ona «özaltçizge» denir.

Tanım 2.7. Bir düğüme çakışık olan çizgilerin sayısına, o düğümün «kertesi» denir.

v, ninci düğümün kertesini d (v;) ile göstere lim. Şekil 2.4 deki çizge için, d (v,) = 3 d (v2) = 2 d( v3) = 3 d (v4) = 3

d (vs) = 3 dür. Tekdüğümlerin kerteleri sıfır alınır. Tanım 2.8. Bir çizgenin ya da altçizgenin çizgilerinden olu şan bir dizi düşünelim, oyie ki bu dizideki her bir çizginin iki uç düğümünden birisine o çir ginin dizide kendinden önce ve sonra gelen çiz gileri çakışık olsun. Bu koşulu sağlıyan çizgi kümesine «çizgi dizisi» denir. Bu tanıma göre bir çizgi dizisinde herhangi bir çizgi birden çok kere bulunabilir. Tanım 2.9. Bir çizgi dizisinde bir çizginin bulunma sa yısına o çizginin «çokluğu» denir. e, çizgisinin çokluğunu m (et) ile gösterelim. O zaman Şekil 2.6 daki çizgeden, («ı. e2, e3, e4, e4, e5, e6, e3> e5, e,) çizgi kümesi bir çizgi dizisi oluşturur. Bu di zideki çizgilerin çoklukları, m (e,) = 1 m(e2) = 1 m (e3) = 2 m (e4) = 2 m(e5) = 2 m (e,) = 1 m (e,) = 1 dir.

Şekil 2.6.

Tanım 2.10. Eğer bir çizgi dizisindeki her çizginin çokluğu bir ise, bu çizgiler bir «çizgi dizgesi» oluştu rurlar.

Geçen örnekteki, (eı e2, e3, e4, e7, e5)

çizgileri bir dizge oluştururlar. Demek ki «her çizgi dizgesi», bir «altçizgedir».

Bir dizgedeki ilk çizginin başka bir çizgi ile çakışmıyan düğümüne dizgenin «başlangıç dü ğümü» (Vj) ve son çizginin başka bir çizgi ile çakışmıyan düğümüne ise dizgenin «sonuç dü ğümü» (vf) denir. Her ikisine birden dizgenin «uç düğümleri» (vt) denir. Yukardakı dizgede Vj ve v3, sırası ile dizgenin başlangıç ve sonuç düğümleridir. Eğer bir dizgede uç düğümleri ayrık ise (vı?sv£) o dizgeye «açık dizge»; çakı şık ise (v2=vf), o dizgeye «kapalı dizge» denir.

Tanım 2.11.

Eğer bir açık çizgi dizgesinin uç düğümleri dışındaki tüm düğümlerinin kertesi 2 ise bu bir «yoldur».

Demek ki her çizgi bir yoldur. Şekil 2.4 den aşağıdaki çizgi kümelerini düşünelim:

PI = (e1( e2)

P2 = (e,, e5, e4, e3)

bunlar birer yoldur. Beri yandan (ej, e5) ve (e1( e2> e3) birer yol değildir.

Tanım 2.12.

G çizgesinde her düğüm çifti arasında en az bir yol var ise G bir «bağlı çizgedir».

Eğer G bağlı çizge değilse, «ayrık çizgedir». G ayrık çizge ise G bağlı altçizgelerin birleşimin den oluşmuş demektir. Ayrık bir çizgenin bağ lı altçizgelerinin herbirine o çizgenin «parçala rı» denir, p, bir çizgenin parçalarının sayısını göstersin. Şekil 2.7 deki çizge 4 parçadan oluş muştur.

G *= G, U G2

G4

(2.11)

ve p=4 dür. Bir çizgede p = l olması o çizge nin bağlı olduğunu gösterir.

Tanım 2.13.

Bir yolun uç düğümleri çakışık ise, buna «çev re» (kapalı yol) denir.

Çevre tanımından, çevredeki düğümlerin ker telerinin iki olduğu hemen anlaşılabilir. Şekil 2.7 deki G çizgesinin G3 parçası ve (e4,e5) çiz gileri birer çevredirler. Beri yandan G2 parça sında bir çevre yoktur. Genellikle kapalı bir çizgi dizgesi yalnız düğümlerde ortak olan çev relerin birleşimidir. Bir çevreyi oluşturabile cek çizgilerden herbirine «çevre öğesi», hiç bir çevreyi oluşturamıyacak bir çizgiye «çevredı

şı öğesi» denir. Şekil 2.7 de e6, e7, e8 ve e^ çiz gileri çevredışı öğeleridir. Diğer tüm çizgıleı çevre öğeleridir.

olan yalnızca iki düğümü bulunduğu demek tir.

Beri yandan G nın bağlı ve kertesi tek sayı olan yalnızca iki düğümü bulunduğunu varsa yalım. Bu düğümler v, ve v2 ile gösterilsinler. v, ve v2 yi e12 çizgisi ile birleştırelim. Bu birleşim den doğan G' çizgesi,

G' = e u U G

Şekil 2.8 de gösterilmiştir. G' çizgesinin tüm dü ğümlerinin kertesi çift sayıya eşittir. Bu tür çizgelere «Euler Çizgesi» denir. Euler çizgesi ka palı bir çizgi dizgesidir, başka bir deyişle yal nız düğümlerde ortak olabilen çevrelerin birle şiminden oluşmuştur. Öyleyse G bir açık çizgi dizgesidir.

11 e

Şekil 2.7.

Teorem 2.1.

Sonlu sayıda öğelerden (çizgi ve düğüm) olu şan G çizgesindeki kertesi tek sayıya eşit olan düğümlerin sayısı çifttir.

Kanıt: r, kertesi i olan düğümlerin sayısı ol sun. G de e kadar çizgi varsa kertelerin topla mı 2e ye eşittir, öyle ise,

2e = r, + 2 r2 + 3 r3 + . + n rn

(2.12)

2e—2 r2—2 r3—4 r4— . = rj+r3 + r5 +. . (2.13)

Denklem 2.13 ün sol yanının çift sayıya eşit ol duğu kolayca görülebilir. Bu da, sağ yanının da çift sayıya eşitliği demektir.

Öyleyse,

I r2l+ı = çift

1=0

Teorem 2.2. (Listing)

G çizgesinin, açık çizgi dizgesi olması için ge rek ve yeter koşul, G nin bağlı olması ve ker tesi tek sayı olan yalnızca iki düğümünün bu lunmasıdır.

Kanıt: Eğer G bir açık çizgi dizgesi ise, bu, Tanım 2.10 dan G nin bağlı ve kertesi tek sayı

Şekil 2.8. Listing Teoreminin ilginç uygulamaları bir çok bulmacalarda görülebilir. Örneğin Königs berg Köprülerini düşünelim. Şekil 1.1 e ilişkin çizgeyi; A, B, C ve D düğümler ve köprüler de çizgiler olarak alındığında, Şekil 2.9 da olduğu gibi gösterebiliriz. Burada kertesi tek sayı olan

Şekil 2.9. dört düğüm bulunduğundan bu sorunun çözü mü yoktur. Başka bir örnek şöyle verilebilir: Şekil 2.10 da kesik çizgilerle gösterildiği gibi ka lemi kaldırmadan her çizgiden yalnızca bir ke

re geçilebilir mi, geçilemez mi? Şekil 2.11 de gös terilen ilişkin çizgeye bakıldığında A, B, C, D, E ve F düğümlerinin kertelerinin d (A) = 5, d ( B ) = 5 , d ( C ) = 4 , d (D) = 5 , d (E) = 4, d (F) = 9 olduğu görülür. Demek ki burada da ikiden çok tek sayıh kertesi olan düğüm bulun duğundan bu sorunun da çözümü yoktur.

Şekil 2.10.

"*

S

/

/ S

S / \

V V

Tanım 2.15.

G nin p kadar parçası olsun,

G = G, U G2 U G3 U • • • U Gp ve T,, G, nin içinde seçilen bir ağacı göstersin. O zaman,

T = T, U T2 U T3U bir «ormandır».

... U TD

Tanım 2.16.

Bir ağacın tümleraltçizgesine «tümleıağaç» de nir.

Tanım 2.17.

Bir ormanın tümleraltçizgesine «tümlerorman» denir.

Tanım 2.18. Ağacın ya da ormanın bir çizgisine «dal» denir.

Tanım 2.19.

Tümlerağacın ya da tümlerormanın bir çizgi sine «kiriş» denir.

Şekil 2.11.

Artık, çizge kuramının en temel kavramını ta nımlayabiliriz.

Tanım 2.14. G çizgesinin aşağıdaki özellikleri sağlıyan T altçizgesine «ağaç» denir. (i) T bağlıdır, (ii) G nin bütün düğümleri T nin de düğüm leridir, (iii) T nin hiçbir altçizgesi çevre yapmaz, (iv) T de yalnızca v—1 kadar çizgi vardır.

Teorem 2.3. Her bağlı çizgede en az bir ağaç vardır. Bu teoremin kanıtı düşünme olanağı sağlamak için okuyucuya bırakılmıştır.

Şekil 2.12.

Şekil 2.12 de gösterilen G çizgesini düşünelim. G de dokuz tane değişik ağaç seçilebilir. Bun lar,

T, = ( e 2 > e3, e4, e 5 ) T 2 = (e,, e2, e4, e6) T3 = (e,, e3, e5, e6) T4 = (e1( e2, e5, e6) T5 = (e,, e3> e4, e6)

T« = (e2, e3, e4, e6) T7 = (e* e3, e5, e6) T8 = (e1( e2, e4, e5) T, = (e,, e3, e4, es)

dir. Bu ağaçlara karşıt olan tümlerağaçlar ise sırasıyle şunlardır :

T', = (e,, e6) T'2 = (e3, e5) T', = (e2, e4) T'4 = (e,, e4) T's = (e2, e5)

T'« = (e,, e s ) T'7 = (eIf e4)

T', = (e,, e6) T'9 = (e2, e6)

Teorem 2.4.

T a n ı m 2.14 de verilen özelliklerden herhangi üçü dördüncüsünü kanıtlar.

Bu teoremin kanıtı da okuyucuya bırakılacak ve aşağıdaki teoremin kanıtı verilecektir.

Teorem 2.5.

Tanım 2.14 deki (m) ve (iv) üncü özellikler öbür iki özelliği kanıtlamaya yeterdir.

Kanıt : (iii) T nin hiçbir altçizgesi çevre yap maz.

(iv) T de yalnızca v—1 kadar çizgi vardır.

Verilen T altçizgesinin p kadar parçası oldu ğunu ve (iii) ile (iv) deki özellikleri sağladığı nı varsayalım.

T = T,

U TB

T, de v, kadar düğüm varsa T, nın v—1 kadar çizgisi var demektir, v, T deki düğüm sayısını gösterirse,

v = î v,

(2 14)

Kanıt: Denklem 2.17 endüksiyon yolu ile ka nıtlanabilir. Verilen bir çizgede, k = e —b olduğundan, denklem 2.16 nın da doğruluğu görülebilir.

Tanım 2.22.

Bağlı bir G çızgesmin seçilen T ağacına göre «t çevreleri» (temel çevreleri) k kadar kirişle rin birer birer tanımlayacakları tek bir kiriş ve birik ağaç dallarından oluşan çevrelerdir.

Eğer G bağlı değilse t çevreler seçilecek bıı ormana göre tanımlanırlar. Böylelikle, G çı/. gesinin t çevrelerinin sayısı çizgenin sıfııiığma eşittir. Şekil 2.13 deki çizgede T ağacının,

T = (e,, e2> e4, e5, e8)

(2.18)

dir. Ama T nin çizgilerinin sayısı her bir T, deki çizgilerin toplamına eşit olacağından,

2 (v,—1) = 2 v, —p

=

ı=. l

= v—p = v—1

(2.15)

olarak yazılabilir. Bu da p = 1 olduğunu gös terir ki, başka bir deyişle T nin bağlı olduğu nu kanıtlar.

Böylelikle (iii) ve (iv) üncü özelliklerin (i) inci özelliği kanıtladığını göstermiş olduk. Teorem 2.4 kullanılarak geri kalan kısım ta mamlanabilir.

Tanım 2.20.

Bir çizgedeki kiriş sayısı k ye, o çizgenin «sı fırlığı» denir.

Tanım 221.

Bir çizgedeki dal sayısı b ye, o çizgenin «aşa ması» denir.

Teorem 2.6.

v, e ve p kadar, sırasıyla, düğümü, çizgisi ve parçası olan G çizgesinin sıfırlığı,

k=e—v+p

(2.16)

ve aşaması

(2.17)

olarak seçildiğini düşünürsek tanımlanacak t çevreler, ct, = (e,, e2, e3) ct2 = (e4, e5, e6, eâ) ct3 = (e4 e5 ^ e8) dir ve sayısı, k=e—v+p =8—6+1=3 Ağaca ilişkin çevre gibi, başka bir temel kav ram kesitlemedir.

Tanım 2.23. Aşaması b olan G çizgesinin aşağıdaki iki özel liği sağlıyan altçizgesi Gx e «kesitleme» denir. (i) Gx, G den çıkarıldığında elde edilen çiz genin aşaması b — 1 dir. (ıı) Gx in başka hiç bir ozaltçizgesı G den çı karıldığında elde edilen çizgenin aşaması b den değişik olmaz. Tanım 2.23 deki G çizgesi eğer bağlı ise Gx, G den çıkarıldığında G iki parçadan oluşan bir

çızgeye indirgenir. Kesitleme kavramını açık lamak için Şekil 2.13 deki çizgeyi düşünelim Burada,

G: = (e,, e2) G2 = (e4, e6, e7)

(e2, e3, e4, e8 G4 (e2, e3, e6)

altçızgeleri düşünüldüğünde Gj ve G2 nın ke sitleme oldukları görülür. Beri yandan G3 un çıkarılması aşamayı iki düşüreceğinden, bu bir kesitleme değildir. Bu durumda tekdüğüm v, de bir parça olarak düşünülmektedir. G4 ün e? ve e3 den oluşan altçizgesi de aşamayı bir azaltacağından G4 de kesitleme değildir, t çev relerde olduğu gibi, seçilecek bir ağaca göre temel kesitlemeler de tanımlanabilir.

Tanım 2.24.

Bağlı bir G çizgesinin, seçilen T ağacına gorc «t kesitlemelerı» (temel kesitlemeleri) b kadaı dalların birer birer tanımlıyacakları tek bir dal ve birik tümlerağaç kirişlerinden oluşan kcsıt lemelerdir.

Tanım 2.24 deki G çizgesi eğer bağlı değil ise, t kesitlemeleri seçilecek bir ormana göre tanım lanırlar. Çizgenin aşaması, çizgedeki t kesııle melerinifı sayısına eşittir. Yine Şekil 2.13 deki çizgeyi ve denklem 2.18 de verilen ağacı düşü nürsek tanımlanabilecek kesitlemeler şöyle sı ralanabilir :

x,, = (e,, e3) xı2 = (e,, e,) x,, = (e4, e,, e7) x,4 = (e,, e(,, e7)

x,, = (e6, e7, es)

Görüldüğü gibi t kesitlcmc sayısı,

= 6—1 = 5 olarak bahınur

3. YÖNLENDİRİLMİŞ ÇIZGELERİN DOKU SAL MATRİSLERİ

Buraya kadar yönlendirilmemiş, ya da çizgi lerine bir yon verilmemiş, çizgelerden soz et tik. İlerde karşılaşacağımız sorunlara çözüm verebilmeleri için bundan böyle düşüneceğimiz çızgelerdeki çizgilere birer yön koyacağız. Baş ka bir deyişle artık yönlendirilmiş çizgeler üze rinde uğraşacağız Şekil 3.1 de \ önlendirilmiş bir çızge gösterilmektedir. Buradaki eı çizgisini düşünelim. Bu çizgiye verilen yon Vj den v2 ye doğrudur ki, anlamı, ej üzerinden yapılacak bir geçiş eğer çizgiye konan okla ayni yönde ise artı, ters yönde ise eksi olarak onanacak

tır. Yön kavramını saptadıktan sonra artık ve rilen bir çizgeyi belirliyecek dokusal matris leri tammlıyabiliriz.

Tanını 3.1. Eğer e ve v sırasıyla G çizgesindeki çizgi ve düğuın sayısını gösteriyorsa v kadar dizeği ve e kadar dikecı olan «çakışım» (düğüm) mat risi n = ÜTî,,]* c aşağıdaki gibi yazılabilir.

Eğer e, çizgisi v, duğümu ile çakışık ve yönü v, den uzakiaşiyorsa : ıtu = 1

Eğer e, çizgisi \\ düğümü ile çakışık ve yönü v, ye geliyorsa : TI,, = — 1

Eğer e, çizgisi v] düğümüne çakışık değilse:

Bu tanıma göre Şekil 3.1 deki çizgenin çakışım matrisi,

c9

0ooo

ooü1

(3.1)

1o o ı

o 1oo

o —1 —1

olarak yazılır. Çakışım matrisinin özelliklerin den önemli olan ikisi şunlardır :

a. Her dikeçte sıfır olmayan yalnız iki öğe vardır.

b. g (1 < g < v) boyunda herhangi bir behı teninin değeri 1, —1 ya da 0 dır.

Bunlardan ilki hemen görülebilirse de, ikinci si biraz düşünme gerektirmektedir.

Dizek ve dikeçlerinin sırasını uygun düzen liyerek çakışım matrisinin,

(3.2)

olarak yazılabileceğini düşünürsek buradan çı kacak sonuç n nin karşıt olduğu çizgede p kadar parça vardır demektir.

Tanım 3.2.

Bağlı bir çizgenin çakışım matrisinin rasgele bir dizeğinin çıkarılması ile elde edilecek n matrisine «indirgenmiş çakışım matrisi» denir.

Tanım 3.2 ve çakışım matrisinin ilk özelliğin den, indirgenmiş çakışım matrisi verildiğinde buradan çakışım matrisinin yazılabileceği ko

laylıkla görülebilir, n matrisinin en büyük özelliği bunun v—1 boyundaki herhangi bir altmatrisinin belirtisinin sıfırdan değişik olma sı için yeter ve gerek koşulun, bu altmatrisin dikeçlerinin çizgedeki bir ağaca karşıt olma larıdır.

Tanım 3.3.

e kadar çizgisi olan G çizgesinde, d kadar ras gele yönlendirilmiş çevre olsun. «Çevre matri si» B = [ b ı J ] d e aşağıdaki gibi yazılabilir.

Eğer ej çizgisi cf çevresinde ve özdeş

ise : K = 1

Eğer e, çizgisi

ise : b .

çevresinde ve ters

yönde yönde

Eğer e, çizgisi cı çevresinde bulunmuyorsa: b,, = 0

Şekil 3.2 deki G çizgesindeki altı çevre, c, = (e,, e2) c, = (e2, e3, e4) c3 = (eı# e3, e4) c4 = (e4> e5, e6) c5 = (e,, e3, e5, e6) c6 = (e,, e3, e5, e6)

olarak tanımlanabilir. Herbirine, şekilde belir tildiği gibi rasgele bir yön verelim, o zaman bu çizge için çevre matrisi,

—1 1 0 0 0 0 0 —1 1 1 0 0

—1 0 1 1 0 0

B=

0 0 0 —1 1 1

—1 0 1 0 1 1

0 —1 1 0 1 1

(3.3)

olarak bulunur. Şekilden de görülebileceği gibi örneğin, c,, c2 ve c3 çevreleri bağımsız değildir. Başka bir deyişle Cj ve c2 nin bilinmesi c3 ün de bilinmesi demektir. Bir genellemeye gidilir se B deki bağımsız çevreler, ya da B matrisi nin aşaması rB,

rB = e —v + p =k

(3.4)

Tanım 3.4.

Bir çizgede seçilecek ağaca göre kirişlerin ta nımlıyacağı t çevrelerin yönleri tammlıyan kiriş lerin yönlerine özdeş alınarak yazılacak B, matrisine «t çevre matrisi» (temel çevre) de nir.

Böylelikle Tanım 3.4 den Bf matrisinin her za man,

Bf = [B, U] (k)

(3.5)

olarak yazılabileceği görülür. Denklem 3.5 de U kxk boyutunda birim matris olup, B, ve U nun dikeçleri sırasıyla çizgedeki dal ve kiriş lere karşıttır. Şekil 3.2 de,

T = (e,, e3, e5)

(3.6)

olarak seçilen bir ağaca göre t çevre matrisi

e, e, ıı

1j

O1 0o 1O

e4 (3.7)

dir. Bu özel örnekte denklem 3.6 da gösterilen ağacın tümlerağacınm da bir ağaç olmasından ötürü Bj altmatrisinin de belirteninin sıfırdan değişik olduğu görülür.

Tecrem 3.1.

Bir çizge için çevre ve çakışım matrislerinin dikeç sıralamaları özdeş alınırsa,

B nr = o

(3.8)

(3.9)

olur.

Kanıt: Denklem 3.8. ve 3.9 birbirlerinin devri ği olduklarından yalnız birini kanıtlamak ye terlidir, b, ve jt, çevre ve çakışım matrislerinin i ve j yinci dizekleri olsunlar,

b, n T = s

(3.10)

Denklem 3.10 daki çarpımda sıfırdan değişik bir terim çıkması için çizgilerin bir kısmının hem j yinci düğüme çakışık hem de i ninci dev re içinde olması gereklidir. Bu durum Şekil 3.3 de gösterilmiştir ve bu çizgiler ancak ya hiç yoktur ya da biri + 1 diğeri —1 olarak kesinlik le ikidir. Tüm yönlenme durumları incelendiğin de s — 0 görülür.

e 2

0—11010

0—1001

—1 0 0 — 1 —1 —1

(3.11)

elde edilir ki, buradan da Teorem 3.1 in sağ landığı kolaylıkla görülebilir.

Tanım 3.5.

Bir çızgede x kadar kesitleme olsun ve bun lara rasgele yönler verilsin, bu çizge için «ke sitleme matris» A = [a,,]^,. aşağıdaki gibi ta nımlanır :

Eğer ct çizgisi xL kesitlemesinde ve özdeş yön de ise : aı( = 1

Eğer e, çizgisi xı kesitlemesinde ve ters yönde ise : atl = —1

Eğer eL çizgisi xt kesitlemesinde değilse: a,, = 0

Şekil 3.4 de verilen G çizgesinde,

X l = ( e i e2> e3> x2 = (e,, e4, e6) x3 = (e3, e5, e6) x4 = (e^ e4, e5)

X5 = (el

2' e5>

x6 = (e,, e3, e4, e5)

x7 = (e2, e3, e4, e6)

olmak üzere yedi kesitleme vardır. Şekilde de gösterildiği gibi bu kesitlemelere gelişigüzel

Şekil 3.3. Şekil 3.2 deki çizgenin çakışım matrisi denk lem 3.3 e göre yeniden düzenlendiğinde.

Şekil 3.4.

yönler verilmiştir. Bu duruma karşıt kesitleme matrisi,

c

1 —1 —1 o o o

1 O 0—101

X2

oo 1

0 — 1 — 1 X3

A=

O1

1—1

o O —1 —1

1 —1 —1

x4 (3.12) xs

O —1 —1 —1 o

X6

X7

oiarak yazılır. Çevre matrisinde yapılan benzer

düşünce ile kesitleme matrisinin aşamasının

(rA),

r. = v p = b

(3.13)

olduğu görülebilir.

Tanını 3.6.

Bir çizgede seçilecek ağaca göre dalların ta nımlayacağı t kesitlemelerin yönleri tanımlı yan dallara özdeş alınarak yazılacak Af matri sine «t kesitleme matrisi» denir.

Böylelikle, verilen bir çizge için Af matrisinin her zaman,

Af = [U A.] (b)

(3.14)

olarak yazılabileceği görülür. Şekil 3.4 deki çiz gede,

T = (e2( e4, e5)

(3.15)

olan bir ağacın seçildiğini onaylıyalım. Bu du rumda,

= r 0ı

0 1

0 —1 01

1 0

0 0 1 0 —1 1

(3.16)

elde edilir. Buradan Af in b boyutundaki bir altmatrisinin belirteninin sıfırdan değişik ol ması için karşıt dikeçlerinin bir ağaç oluştur ması koşulu ortaya çıkar.

Teorem 3.2.

Verilen bir çizge için yazılacak çevre ve ke sitleme matrislerinin dikeç düzenleri özdeş ol duğundan.

A BT = 0

(3.17)

B Â~T = 0

(3.18)

dır.

Teorem 3.2. nin kanıtlanması, Teorem 3.1 e benzediğinden burada buna değinmeyeceğiz.

Teorem 3.3.

Ozdcş dıkeç düzeninde, bir çizge için t çevre ve t kesitleme matrisleri aşağıdaki gibi veril miş olsunlar,

Bf = [B, U] Af = LU A,] Bu durumda,

(3.19) (3.20)

A, = Bj dir.

(3.21)

Kanıt: Teorem 3.2 den,

[U A,]

B J t A, = 0

P, m x n boyunda bir matris olsun. Eğer m < n ise P nin m x m; m > n ise, n x n boyundaki alt matrislerinin belirtenlerine bu matrisin «ana belirtenleri» denir.

Teorem 3.4. (Binet Cauchy) P ve Q sırasıyla m x n ve n x m boyunda mat risler olsun. PQ matrisinin belirteni, i p^ . i _, P ve Q nun karşıt olan • • ~ ** ana belirtenlerinin çarpımları

Teoremdeki toplam, tum ana belirtenler için alınmalıdır.

Teorem 3.5.

Bağlı bir çizgede yazılabilecek tüm ağaçların sayısı t ise, t = |nnT|

Kanıt: Teoremin kanıtı Binet Cauchy Teoremi ve Af( Bf ya da n matrisindeki bir ana belir tenin değerinin, yalnızca karşıt dikeçler bir ağaç ya da tümlerağaç oluşturduklarında + le eşit ve diğer durumlarda sıfır olmasından ge lir.

Şekil 3.5.

Teorem 3.5 in uygulaması olarak Şekil 3.5 deki çizgeyi düşünelim, e, ve e2 seçilen ağaç olsun. Bu durumda,

1 —1 —1 — 1

n = —1 —1

|nnr| =

4 —1

—1 = 7

(3.22)

eı

e2

e_,

e5

Af =

1 —1 —1 —1

=7

(3.23)

10 0

1Ü

Bf

(3.24)

olarak bulunur. Böylelikle verilen bir çizgenin sıfırlığı ya da aşamasından kimi küçükse denk lem 3.22, 3.23 ya da 3.24 kullanılarak çizgedeki toplam ağaç sayısı bulunabilir.

Buraya kadar çizge kuramının temel kavram ları ile dokusal matrislerinin tanımlarını yap mış oluyoruz. Bu yazı dizisinin ikinci bölümün de bazı özel tür çizgelerden söz ettikten sonra devre kuranımın temel konutlarını ortaya koya rak uygulamalara geçeceğiz.

YAZIDA GEÇEN TERİMLERİN İNGİLİZCE KARŞILIKLARI

Ağaç — Tree Altçizge — Subgraph Ana Belirten — Princıple Determinant Aşama — Rank Ayrık Çizge — Separated Graph Bağlı Çizge — Connecıed Graph Başlangıç Düğümü — Initial Vertex Belirten — Determinant Birleşim — Union Boşçizge — Null graph Çakışım — Incidence Çevre — Circuit Çevre öğesi — Circuit Element Çevredışı Öğesi — Noncircuit Element Çizge — Graph Çizgi — Edge Çizgi Dizisi — Edge Sequence Çizgi Dizgesi — Edge Train Çizginin Çokluğu — Multiplicity of an Edge Çözümleme — Analysis Dal — Branch Devrik — Transposed Dikeç — Column Dizek — Rovv Doku — Topology Düğüm — Node (Vertex) Düğümün Kertesi — Degree of a Vertex İndirgenmiş — Reduced Kanıt — Proof Kesitleme — Cutaet Kesişim — Intersection Kiriş — Chord Kuram — Theory Orman — Forest Özaltçizge — Proper Subgraph Parça — Parts, Maximally Connected Subgraphs Sıfırhk — Nullity Sonuç Düğümü — Final Vertex Tekçevre (Özçevre) — Selfloop Tekdüğüm — Isolated Vertex Temel — Fundamental Tümler — Complementary Tümlerağaç — Cotree Tümlerorman — Coforest Uç Düğümleri — Terminal Vertices Üstçizge — Supergraph Yol — Path Yönlendirilmiş — Oriented