ÇİZGE KURAMININ TEMELLERİ 2

UDK: 518.83

Çizge Kuramının Temelleri 2

Yurdakul CEYHUN

ÖZET

Bu yazıda çizge kuramının diğer kavramları verilerek temel konutlar ve örü çözümlemesi nin ana ilkeleri ortaya konmuştur.

SUMMARY

Further properties and the fundamentat pos tulat es of graph theory are stated and the main analysis procedure for networks is outli ned.

4. DÜZLEMSEL ÇİZGELER VE İKİLEMLİK

Çizgelerin özelliklerine göre ayrımları yapıldı ğında düzlemsellik önemli bir etken olarak or taya çıkmaktadır.

Tanım 4.1

Bir düzleme, çizgileri düğümlerden başka yer lerde çakışmadan çizilebilen çizgelere «düzlem sel» çizgeler denir.

Şekil 4.1a'da 3 boyutlu uzaya çizilmiş çizge, Şekil 4.1b'de çizgileri düğümlerden başka yer lerde çakışmadan 2 boyutlu uzaya, düzleme, yeniden çizilebilmiştir. Dolayısı ile bu bir düz lemsel çizgedir.

Tanım 4.2

Kertesi kesinlikle iki olan vo düğümü, eğer e, ve e, çizgilerinin ortak çakıştıkları tek düğüm ise, bu çizgiler «ardıl bağlıdırlar».

e;

(a)

Şekil 4.1.

Yurdakul Ceyhun, Y. Prof. Dr., Elektrik Mühendisliği Bö lümü, Ortadoğu Teknik Üniversitesi, Ankara Bu yazının birinci bölümü dergimizin 205 206. Sayısında (sayfa 47 58) çıkmıştı.

Şekil 4.2.

Şekil 4.2 de ardıl bağlanmış iki çizgi görül mektedir.

Tanım 43 V,, V2, V3, V4, V5 diye adlandıracağımız beş dü ğümden oluşan bir düğüm kümesi düşünelim. Eğer bu kümedeki her düğüm çiftinin arasın da bir çizgi ya da ardıl bağlanmış çizgiler var

sa buna «Birinci Tür Kuratovvski Çizgesi» (Kİ) denir.

Tanım 4.4 v ı V2, V3 ve V4, V5, V6 diye adlandırılan dü ğümlerden oluşan iki ayrı düğüm kümesi dü şünelim. Eğer bu kümelerden her birinin dü ğümü diğerinin büıün düğümlerine bir ya da ardıl çizgilerle bağlanmış ise buna «îkinci Tür KuratOA'ski Çizgesi» (K2) denir.

Şeldl 43.

Şekil 4.3a ve 4.3b'de, sırasıyla, Kİ ve K2 için birer örnek verilmiştir. Şimdi bir çizgenin düz lemselliğini saptıyan ana tanıtlanması bu ya zı dizisinin çok ötesinde olan bir teoremi su nacağız.

Teorem 4.1

Bir çizgenin düzlemsel olabilmesi için gerek ve yeter koşul, hiç bir tür Kuratowski çizge sinin bu çizgenin bir altçizgesi olmamasıdır.

Düzlemsellik kavramının ve Teorem 4.1'in il ginç bir uygulaması olarak şu bulmacayı düşü nelim. Şekil 4.4a'da gösterildiği gibi yanyana üç evde (A, B, C) üç düşman kişi oturuyorlar. Her birinin evinin karşısında birer kuyu var (1, 2, 3). Her biri bu üç kuyuya birbirleri ile kesişmeyen birer yol yapmak istiyorlar. Aca ba bu sorunun çözümü var mıdır?

Şekil 4.4a, 4.4b deki gibi yeniden çizilirse bu nun bir ikinci tür Kuratovvski çizgesi olduğu görülür. Demek ki bu bulmacanın da çözümü yoktur.

Düzlemsel çizgelerin önemli bir özelliği de ve rilen bir düzlemsel çizgeye ikilem olan diğer bir çizgenin var oluşudur. İkilem çizgenin ta nımı şöylece verilebilir.

Tanım 4.5

Çizgileri arasında bire bir karşıtlık olan G, ve G2 çizgelerini düşünelim. Hv G^n gelişi güzel bir altçizgesi olsun. H, in Gj deki tümler alt

Şekil 4.4.

çizgesinin G2 deki karşıtına H2 diyelim. r2 ve R2 sırasıyla H2 ve G2 nin aşamaları ve n, de G, in sıfırlığı olsun. Seçilebilecek her Ht için

r2 = R2 — n ,

(4.1)

bağlantısı sağlanıyor ise, G, ve G2 birbirlerinin «ikilemleridir».

Teorem 4.2

Her düzlemsel çizgenin birik bir ikilemi vardır. Bu teoremin de tanıtını vermiyerek, ikilem çizgenin elde edilmesi için kolaylıkla uygula nabilir bir yol göstereceğiz. Şekil 4.5'de göste rilen çizgeyi düşünelim. A, B ve C ile adlan dıracağımız birer düğümü, (a, b, d), (b, c, e) ve (d, e, f, g) çizgileri ile tanımlanan birer ka palı bölgeye (göz) yerleştirelim. Diğer bir dü ğüm D ise dış bölgeye konsun. A ve D düğüm lerinin konduğu bölgeleri ayıran a çizgisini ke serek bu iki düğümü birleştiren çizgiye a' diye lim. Bu yolu izliyerek A, B, C ve D deki her düğüm çiftini, verilen çizgenin çizgilerini yal nız birer kez keserek yeni çizgilerle birleştire lim. Elde edilecek ve düğümleri A, B, C ve D olan bu yeni çizge (G2) Gj in ikilemidir. Gt ve G2 çizgelerinin ikilemlikleri Tanım 4.5'in uygu alınması ile kolayca görülebilir. G2 deki çizgile rin yönlendirilmesi ise şöyle yapılabilir. V dü ğümünün konduğu bölgeyi tanımlayan çizge lerden birinin (e) yönü Vye göre saat dönme yönünde (tersi) ise e çizgisini kesen e' çizgisi V düğümünden uzaklaşıyordur (düğümüne ge liyordur).

Birbirlerinin iklemi olan G, ve G2 çizgelerini düşünelim. Kolaylıkla görülür ki, G, de bir ağaç (tümlerağaç) oluşturan çizgilerin G2 deki karşıtları bir tümlerağaç (ağaç) oluşturmak tadır. Bu gözlenimin sonucu olarak aşağıdaki teorem verilebilir.

Teorem 4.3

Düzlemsel bir çizgenin çevre ve kesitleme matrisleri, bu çizgenin ikileminde sırasıyla ke sitleme ve çevre matrislerine dönüşürler.

Örnek olarak Biçim 4.5 deki Gt ve G2 çizgele rini düşünelim G, in çakışım matrisi ft.

1 110000

~

v —1 0 0 —1 0 1 0

0 —1 0 1 —1 0 0

vVe4

0 0 —1 0 1 0 1 0 0 0 0 01 1

(4.2)

dir. G2 nin çakışım matrisi TC2 i s e

A B c 7T2 = D

a' b ' c' d' e' F g'

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

(4.3)

dir. (a, b, e, f) Gj çizgesinde seçilen bir ağaç olsun. Bu ağaca göre Bıf

d Bıf = e

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

—1 0 1 —1 0 0 1

(4.4)

olarak bulunur. G, deki bu ağaca karşıt G2 de ki ağaç (d', e', g') çizgilerinden oluşur. Böylelik

le G2 deki ]32f

a' b ' c' F d' e' g

a'

BM = b' c' F

1000 10 1 0 1 0 0 —1 1 0 0 0 1 0 0 —1 j 000100 1

(4.5)

dir. Benzer işlemler kesitleme den klen yapıldığında

Aıf = b c f

1000 10 1 0 1 0 0 —1 1 0 0 0 1 0 0 2 —1 000100 1

(4.6)

d' = e> g'

b"

f d'

110 0 10 0

0—110010

(4.7)

1 0 1—1 0 0 1

olduğu görülür. Buradan bir genelleme yapıl dığında birbirlerine ikilem olan çizgeler için

Bıf =

(4.8)

ve A —R

(4 9}

bulunur. İlginç bir sorun da ikilem çizgelerin

çakışım matrisleri ıtı. TJZ arasında bir ilişki bu lunup bulunamıyacağıdır ki bu sorunu düşü nülmek üzere okuyucuya bırakacağız.

5. ÖRÜLERE UYGULAMA VE TEMEL KO NUTLAR

Şimdiye dek yalnızca çizgelerden söz ettik ve bunları oluşturan çizgilere bir anlam verme dik. Rasgele öğelerden oluşan bir örü düşünür sek, bu öğelerin uçlarına ilişkin tanımlıyacağı mız çizgilerden oluşan bir çizge bu örünün do kusunu simgesel olarak ortaya koyacaktır, ör neğin Şekil 5.1a daki elektriksel örüyü düşü nelim. Örüdeki öğelerin uçlarına ilişkin ka

pılan birer çizgi ile gösterecek olursak örü nün dokusunu tanımlıyacak çizge kolaylıkla

(a) R

Şekli 5.1.

ortaya çıkar. (Şekil 5.1b). Elde edilen çizgede

ki her bir çizgiye ilişkin iki değişken (bu ör

nekte akım ve gerilim) tanımlıyahm. X geri

limler ve Y akımlar olsun. Bu durumda,

Konut 1 BX = 0

(5.1)

Konut 2 AY = 0 •

(52)

Bu konutlara sırasıyla çevre ve kesitleme ko nutları diyeceğiz. Başka bir deyişle, çizgedeki

her çevre ve kesitleme için, sırasıyla, gerilim ve akımların cebirsel toplamları özdeş olarak sıfırdır. Çizgede seçilen bir ağaca göre yalnız ca temel çevre ve kesitlemeler düşünüldüğün de

U J=

[B, U]

(5.3)

[U AJ

=o

(5.4)

bulunur. Burada b ve c altsimgeleri sırasıyla dal ve kirişleri tanımlamaktadır.

öyle ise,

Yb = A , Y C ve

(5.5)

Xc = B , X b

(5.6)

elde edilir. Denklem (5.5) ve (5.6) dan yapıla

cak gözlem aşağıdaki teoremde olduğu gibi

özetlenebilir.

Teorem 5.1

Çizgesinde e kadar çizgi olan bir örünün top lam 2e kadar bilinmiyenini çözmek için en çok e kadarının bilinmesi gereklidir.

Tanıt

Denklem (5.5) ve (5.6) dan sırasıyla bütün ki riş akımları ve dal gerilimlerinin bilinmesi ile, örüdeki diğer bilinmiyenler olan dal akım ve ki riş gerilimlerinin birik olarak bulunabileceği gö rüîür.

Diğer bir gözlem ise şöylece özetlenebilir.

Teorem 52

Rasgele bir örüdeki akım (Y) ve gerilim (X) değişkenleri arasındaki

X*Y = YTX = 0

(5.7)

ilişkisi her zaman geçerlidir.

Tanıt Denklem (5.3) ve (5.4) den

* Yb

Xr ç

Denklem (5.5) ve (5.6) dan,

X*Y =

XT b

A, Y c

X*

B]

Geçen yazıdaki teorem 3.3 ün denklem (3.21) inden

A, = B j

kullanıldığında Teorem 5.2 kanıtlanmış olur.

6. UÇ DENKLEMLERİNİN KULLANILIŞI

Teorem 5.1'de örüye ilişkin 2e kadar bilinmi yenin en çok e kadarının bilinmesinin ye terli olacağı gösterilmişti. Oysa her çizgiye ilişkin iki değişkenin arasında genellikle bir bağıntı olacaktır, örneğin (n+1) uçlu bir öğe nin n kadar bağımsız kapısına ilişkin n kadar çizgide tanımlanan 2n değişken birbirlerine n + 1 uçlu öğenin «uç denklemleri» diye adlan dırdığımız bir denklem dizisi ile bağlıdırlar. Bu denklemler Laplace uzayında

T X, (s) I _ |"Hn (s) H12 (s) 1 TY, (S) T

[ Y2 (s) J " [H21 (S) 1^ (s) J [ x 2 (s) J (6.1)

olarak yazılabilirler. Denklem (6.1) de tanım lanan öğenin uç gerilim ve akımları sırasıyla,

[" X, (s) I

L x ( ) J X (s) = 2S

(6.2)

r Y (s) = Y,(.> ı

(63)

L Y2(s) J

olsun. Denklem (5.5)'den görülür ki, kiriş akım

ları dilendiği gibi seçilseler bile bu seçim birik

dal akımları tanımlamaktadır. Ya da denklem

(5.6) incelendiğinde dal gerilimlerinin dilendi

ği gibi seçilmesi yine birik kiriş gerilimlerini vermektedir. Beri yandan denklem (6.1), H13 (s) ler ne olursa olsun rasgele verilen Yj (s) ve X2 (s) için birik X, (s) ve Y2 (s) tanımlamak tadır, îşte bu gözlemlerden elde edilen sonuç Xj (s) ve Y2 (s) e karşıt olan çizgilerin sırasıy la ağaç ve tümler ağaçta olmalarını önerir, tik bakışta tersmiş gibi gelen bu yargıya biraz da ha yakından bakalım. Denklem (6.1) deki Y, (s) ve X2 (s) örüyü süren bağımsız kaynaklar ola bilir, dolayısı ile X! (s) ve Y2 (s) her tür ko şuldan uzak yalnızca uç denklemleri ile tanım lanmış olur. Başka bir deyişle bunlar, bir yer de gelişi güzel seçilebilen değişkenler olarak düşünülmelidirler. Dolayısı ile, X! (s) in çizgi leri ağaçta, Y2 (s) in çizgileri ise tümlerağaç ta olmalıdır. İşte uç denklemleri, ve ağaca iliş kin yukarda yaptığımız irdeleme sonucu, bu lunması gerekli bilinmiyenlerin sayısı genellik le e den az olacaktır, örneğin, 2 uçlu R, L ve C öğelerinden oluşmuş devreler için bu sayı bağımsız kaynaklar dışındaki ağaç ya da tüm lerağaçtaki çizgilerin tümüne eşittir.

KAYNAKLAR

Konuyla ilgili araştırmacılara ışık tutabilecek nitelikteki çizge kuramıyla ilgili kaynaklan aşa ğıda sunuyoruz.

1. Benes, V. E., «ıMathematical Theory of Con necting Networks and Telephone Traffic», Academic Press, 1965.

2. Berge, C, «The Theory of Graphs and its Application», Wiley, 1962.

3. Berge, C, «The Theory of Graphs», Met huen, 1962.

4. Berge, C, ve Ghouila Houri, A., «Program ming, Games and Transportation Net vvorks», Wiley, 1962.

5. Busacker, R. B. ve Saaty, T. L, «Finite Graphs and Netvvorks: An Introduction with Applications», McGraw Hill, 1965.

6. Dantzig, G. B., «Linear Programming and Extensions», Princeton University Press, 1963.

7. Deo, N., «An Extensive English Language Bibliography on Graph Theory and its Applications», NASA, Jet Propulsion Lab., California Inst. of Tech., Pasadena, Cal., 1969.

8. Erdos, P. ve Katotta, G,, «Theory of Graphs», Academic Press, 1968.

9. Ford, L. R. Jr. ve Fulkerson, D. R., «Flows in Netvvorks», Princeton University Press, 1962.

10. Frank, H. ve Frish, I. T., «Communication, Transmission and Transportation Net vvorks», Addison Wesley, 1971.

11. Harary, F., «A Seminar on Graph Theory», Holt, Rinehart ve Winston, 1967.

12. Harary, F., «Graph Theory and Theoretical Physics», Academic Press, 1967.

13. Harary, F., «Graph Theory», Addison Wes ley, 1969.

14. Harary, F., Norman, R. Z. ve Cartwright, D., «Structural Models : An Introduction to the Theory of Directed Graphs», Wiley, 1965.

15. Kaufmann, A., «Graphs, Dynamic Program ming, and Finite Games», Academic Press, 1967.

16. Kim, W. H. ve Chien, R. T. W., «Topologi cal Analysis and Synthesis of Communica tion Netvvorks», Columbia University Press, 1962.

17. Kleinrock, L., «Communication Nets Stoo hastic Message Flow and Delay», McGraw HiU, 1964.

18. Koenig, H. E., Tokad, Y., Kesevan, H. K., «Analysis ot Dicrete Physical Systems», McGravvnHill, 1967.

19. Maxwell, L. M. ve Reed, Af. B., «The Theory pf Graphs», Pergamon Press, 1971.

20. Network, Int. Journal (Dergi) 1971 yılından beri Interscience Publishers tarafından ya yınlanmaktadır.

21. Ore. O., «Theory of Graphs», American Mat hematical Society Cambridge CoUoquium Publications, Vol. 38, 1962.

22. Ore, O.:., «Graphs and their Uses», Ran dom House, 1963.

23. Ore, O.:., «The Four Color Problem», Aca demic Press, 1967.

24. Seshu, S. ve Reed, M. B., «Linear Graphs and Electrical Netvvorks», Addison Wesley, 1961.

25. Tokad, Y., «Foundations of Passive Electri cal Network Synthesis», ODTÜ yayınlan, 1971.

26. Turner, J., «Key Word Indexed Bibliog raphy on Graph Theory», Stanford Research Inst. Report. SRİ Project 145591 W. O. A14, Feb. 1964.

27. Tutte, W. T., «Connectivity in Graphs», University of Toronto Press, 1966.

28. Zykov, A. A, «Bibliography on Graph Theory», Theory of Graphs and its Appli cations, Proc. of the Symp. held in Sinole nice, June 1963, Academic Press, 1964.

Yazıda geçen bazı terimlerin İngilizce karşı

lıkları :

Altsimge

— Subscript

Ardıl Bağlantı

— Series Connection

Bölge

— Region

Çizge

— Graph

Çizgi (Ayrıt)

— Edge

Doku

— Topology

Düzlemsel

— Planar

Göz

— Window

İkilem

— Dual

örü

— Network