Sıra | DOSYA ADI | Format | Bağlantı |
---|---|---|---|
01. | Çizge Algoritmaları | ppt | Sunumu İndir |
Transkript
Çizge Algoritmaları 1. ders
Çizge teorisi 1736, Euler, Königsberg Köprüleri problemini çözdü
Königsberg Köprüleri Problemi A B C D
Ch1-4 Çizge örneği 4 öğrenci: A, B, C, D 4 iş: FF, SC, W, BS A B C D FF SC W BS Soru:Tüm öğrenciler arzu ettikleri bir işe girebilirler mi? Cevap: Hayır
Ch1-5 Çizge tanımı G çizgesi (V,E) ikilisinden oluşmuştur. Burada V(G) boş olmayan sonlu bir kümedir (elemanlarına köşe denir) E(G) ise V(G) kümesinde tanımlı bir bağıntıdır ( elemanlarına eğer varsa kiriş denir). V(G) : G nin köşeler kümesi E(G) : kirişler kümesi Kiriş {u, v} = {v, u} = uv (veya vu) G yönlü ise (digraf denir)
Ch1-6 Örnek G=(V,E) olsun V={u, v, w, x, y, z} E={{u,v}, {u,w}, {w,x}, {x,y}, {x,z}} E={uv, uw, wx, xy, xz} G diagram vu w x y z
Ch1-7 u, v : G nin köşeleri u ve v köşeleri G de komşudur eğer uv E(G) ise ( u v ye ve v u ya komşudur) e=uv (e u ve v yi birleştiriyor) (e u ile bağlıdır, e v ile bağlıdır) Komşu ve Bağlı u v e
Ch1-8 Çizge çeşitleri Yönsüz çizge: • (basit) çizge: döngü ( ), katlı kiriş ( ) • Katlı çizge: döngü ( ), katlı kiriş ( ) • Pseudograph: döngü ( ), katlı kiriş ( ) Yönlü çizge: • Yönlü çizge: döngü ( ), katlı kiriş ( ) • Yönlü katlı çizge : döngü ( ), katlı kiriş ( ) Katlı kiriş değil Katlı kiriş döngü Katlı kiriş, parallel kiriş döngü
Ch1-9 Mertebe(order) ve boyut(size) G çizgesinin köşe sayısına çizgenin mertebesi denir (|V(G)| ile gösterilir). Kirişlerin sayısına boyut (|E(G)| ile gösterilir ). Önerme 1: Eğer |V(G)| = p ve|E(G)| = q ise Çizgenin mertebesi p ve boyutu q ise (p, q) çizgesi denir 2 p q
Ch1-10 Çizgelerin uygulanması Ali ve Ahmet Ayşe ve Fatma ile tanışıyorlar. Mehmetle Ahmet ve Fatma tanışıyorlar. Ali Ahmet Ayşe Fatma Mehmet Tanışlık çizgesi:
Ch1-11 Köşelerin derecesi Tanım. G çizgesinin v köşesi için N(v) = { u V(G) | v u E(G) } kümesine bu köşenin komşuluğu denir. v köşesinin derecesi deg(v) = | N(v) | sayısına denir y u v wx N(u) = {x, w, v}, N(y)={ } deg(u) = 3, deg(y) =0
Ch1-12 Not Eğer |V(G)| = p ise 0 deg(v) p 1, v V(G) dir. deg(v) = 0 ise v köşesine tecrit edilmiş köşe denir. v ye tek köşe denir eğer deg(v) tekse. v ye çift köşe denir eğer deg(v) çiftse.
Ch1-13 El sıkışma teoremi Theorem G bir çizge ise, 2|)G(E| )deg( )G(V v v u v wx 2 3 21 8)deg( )G(V v v 4|)(| GE Örnek
Ch1-14 El sıkışma teoremi Özellik Her çizgenin tek köşelerinin sayısı çift sayıdır. ispat. Eğer tek köşelerin sayısı tek sayıda olsaydı, çizgenin toplam derecesi tek olurdu.
Ch1-15 Düzgün çizge Tanım. G çizgesinin her köşesinin derecesi r ise G çizgesine r-düzgün çizge denir. G çizgesi bir r sayısı için düzgünse bu çizgeye düzgün çizge denir 2-düzgün Not. mertebesi 5 olan 3-düzgün çizge yoktur (Özellik) Örnek
Ch1-16 Tümleyen Tanım. G çizgesinin tümleyeni G çizgesidir eğer V(G) = V(G) ve uv E(G) eğer uv E(G). u v w x G u v w x G
Ch1-17 Derece uygulaması Soru: n kişi var (n 2) Bu kişiler arasından hangi iki kişiyi alırsak alalım, bu kişilerin tanıdıkları kişi sayıları bir birinden farklıdır. Bu mümkün mü? ( A B yi tanıyorsa, B de A yı tanıyor)
Ch1-18 Örnek 1 Mertebesi n 2 olan çizgenin dereceleri bir birine eşit olan en az 2 köşesinin olduğunu gösteriniz. ispat. deg(x) = 0 ve deg(y) = n 1 olacak biçimde x ve y köşeleri olmalıdır bu da olamaz (ipucu. Önceki sayfadaki problem.)
Ch1-19 Örnek 2. G çizgesinin mertebesi 14 ve boyutu 25 tir. Köşelerinin derecesi 3 veya 5 tir. Bu çizgenin 3 dereceli kaç köşesi vardır? çözüm. x tane köşenin derecesi 3 olsun, 14 x köşenin derecesi 5 olur. |E(G)| =25 dereceler toplamı=50 3x + 5(14 x) = 50 x = 10
Ch1-20 Örnek 3. G çizgesinin mertebesi 7 ve boyutu 10 dur. 6 köşenin derecesi a ve bir köşenin derecesi b dir. b kaçtır? sol. 6a + b = 20 (a, b) = (0, 20) ( ) (1, 14) ( ) (2, 8) ( ) (3, 2) ( ) a=3, b=2.
Ch1-21 Isomorf(denk) çizgeler v1 v3 v4 v5 u1 u2 u3 u4 u5 G1 G2 G1 ve G2 aynıdır (köşelerin yerlerini değiştirdikten sonra). v2 v2
Ch1-22 Isomorf (denk çizgeler) Tanım. Eğer V(G1) kümesinden V(G2) kümesine öyle bir 1-1 ve örten fonksiyonu varsa ve uv E(G1) ancak ve ancak (u) (v) E(G2) koşulu sağlanıyorsa G1 ve G2 çizgeleri izomorfdur denir(G1 G2 ile gösterilir) fonksiyonuna izomorfizm denir. Önceki sayfada (vi) = ui her i için
Ch1-23 Tanım. Mertebesi 1 olan çizgeye önemsiz çizge denir Örnek 4 Mertebesi 6 ve boyutu 9 olan ve izomorf olmayan 2 tane 3-düzgün çizge bulunuz . G1 G2 Üçgen var Üçgen yok Sol.
Ch1-24 Örnek 5 Aşağıdaki G1 ve G2 çizgelerinin izomorf olup olmadıklarını araştırınız. G1 G2 Üçgensiz Üçgen var Cevap: hayır
Ch1-25 1.4 Altçizgeler Tanım. Eğer V(H) V(G) ve E(H) E(G) ise H çizgesine G çizgesinin altçizgesi denir ( H G) G u v w x y H v w x y G G v w x y F Örnek
Ch1-26 Tanım. S V(G), S olsun. G nin köşeleri S olan en büyük alt çizgesine s den üretilmiş alt çizge denir( <S> ile gösterilir) Üretilmiş Altçizge G u v w x y H G nin üretilmiş altçizgesi değil v w x y H H {xw}∪
Ch1-27 Köşelerin silinmesi Tanım.S V(G) olsun. G S = <V(G) S> olarak tanımlanır Eğer S={v} ise G v yazılır. G u v w x y S={x,u} ise G S u v w x y
Ch1-28 Tanım. X E(G), X olsun. X den üretilmiş alt çizge, G nin kirişleri X olan en küçük alt çizgesidir ( <X> ile gösterilir) Kiriş üretilmiş alt çizge G u v w x y Let X={uv,vw} <X> u v w
Ch1-29 Tanım. H G olmak üzere eğer V(H) = V(G) ise H a örten altçizge denir. Tanım. H = G + {uv, uw} ifadesinin anlamı E(H) = E(G) ∪ {uv, uw} , burada uv, uw E(G). Örnek 6 Eğer H=<E(G)> ise H=<V(G)> olur mu? HayırG u v w H v w
Ch1-30 Örnek G =(p, q) çizge olsun. G nin kaç tane farklı kiriş üretilmiş alt çizgesi vardır? Not. Kiriş üretilmiş alt çizge cevap. 2 q 1 ( X E(G) X , 2 q 1 X )
Ch1-31 Dereceler dizisi Tanım. G=(V, E), V={v1, v2, …, vp} olsun. s: deg(v1), deg(v2), …, deg(vp) dizisine G nin dereceler dizisi denir (Genelliği bozmadan, s artmayan olsun. Bu durumda s tek olarak belirlenir) s: 3, 3, 2, 1, 1, 0G 3 2 13 1 0 minimum derece : (G) maximum derece : (G)
Ch1-32 Eğer d1, d2, …, dp bir çizgenin dereceler dizisi ise 0 d i p 1 i. ve çifttir. s: d1, d2, …, dp tam sayılar dizisi ve 0 d i p 1 i, ve çift ise s in dereceler dizisi olduğunu söyleyemeyiz. örnek. s: 5, 5, 3, 2, 1, 0 Not 1 p i id 1 p i id Daha fazlası, d1 p imkansızdır. ) ( p 1 ve 0 aynı zamanda olamazlar)
Ch1-33 Tanım. Negatif olmayan tam sayılar dizisi verilmiş olsun. Eğer dereceleri bu dizinin elemanlarına eşit olan bir çizge varsa bu diziye grafiksel dizi denir Theorem 2 (Havel-Hakimi) s dizisi: d1, d2, …, dp, burada di N, i. olsun. t dizisi : olsun. s in grafikseldir ancak ve ancak t grafikseldir. pddd dddddd ,,,,1,,1,1 32132 111
Ch1-34 İspat : pddd dddddd ,,,,1,,1,1 32132 111 v1 G1 … v2 v3 vd1+1 vd1+2 d2 1 d3 1 vp … dd1+1 1 dd1+2 dp ( ) Eğer s1 : grafikselse G1 de s1 dereceler dizisidir d2 d3 G … v2 v3 vd1+1 vd1+2 vp … dd1+1 dd1+2 dp … s : d1, d2, …, dp grafikseldir d1 köşeler
Ch1-35 ( ) Eğer s : d1, d2, …, dp grafikselse G çizgesi var yani s dereceler dizisidir G ve deg(vi) = di for 1 i p, ve maksimumdur İspat devam )( 1 )deg( vNw w iddia: { v1v2, v1v3, …, v1vd1+1} E(G) v1 G … v2 v3 vd1+1 vd1+2 d2 d3 vp … dd1+1 dd1+2 dpd1 : : i.e., Bu iddia doğru ise, bu durumda G-v1 çizgedir dereceler dizisi s1 s1 grafikseldir
Ch1-36 doğru değilse öyle iki vj ve vk (j < k) köşeleri vardır ki dj > dk yani v1vk E(G) ama v1vj E(G). İddia: { v1v2, v1v3, …, v1vd1+1} E(G) ispat: v1 G vj vk vn dj > dk olduğundan vn V(G) yani vjvn E(G), vkvn E(G). G2 = G {v1vk, vjvn} + {v1vj, vkvn} )( 1 )deg( vNw wG2 nin derece dizisi s ama büyük ,
Ch1-37 Algoritma s: d1, d2, …, dp tam sayılar dizisidr s grafiksel midir?: (1) Eğer di=0, i, ise s grafikseldir. Eğer di<0 bir i için ise s grafikseldir. Aksi durumda, (2). Adıma git (2) s i artmayan şekilde sırala (3) s = s1 olsun(s1 Teorem ), (1) e dön
Ch1-38 Örnek 1 s: 4, 4, 3, 3, 2, 2 s1’: 3, 2, 2, 1, 2 ( 4 ü sil) s1: 3, 2, 2, 2, 1 (sırala) s2: 1, 1, 1, 1 (3 ü sil) s3’: 0, 1, 1 (ilk biri sil 1) s3: 1, 1, 0 (sırala) s4: 0, 0 (ilk1 i sil) s grafiksledir
Ch1-39 Çizge çizimi s: 4, 4, 3, 3, 2, 2 s1’: 3, 2, 2, 1, 2 s1: 3, 2, 2, 2, 1 s2: 1, 1, 1, 1 s3’: 0, 1, 1 s3: 1, 1, 0 s4: 0, 0 s grafikseldir G 4 42 2 3 3
Ch1-40 Örnek 2 s: 5, 4, 3, 2, 1, 1 s1: 3, 2, 1, 0, 0 (5 i sil) s2: 1, 0, -1, 0 (3 ü sil) s grafiksel değil