Grafik ve Grafik Modelleri
Önceki bölüm muhakeme, ispat ve problem çözme için farklı araçları ortaya koydu. Bu bölümde, birçok gerçek hayat problemini formüle etmenin temelini oluşturan ayrık yapıları inceleyeceğiz.
Ele alacağımız iki ayrı yapı, grafikler ve ağaçlardır. Grafik, kenar adı verilen bir dizi çizgiyle birbirine bağlanan düğümler veya köşeler adı verilen bir dizi noktadır. Grafiklerin incelenmesi veyagraph theory matematik, mühendislik ve bilgisayar bilimi alanlarında bir dizi disiplinin önemli bir parçasıdır.
Grafik nedir?
Definition - Bir grafik ($ G = (V, E) $ olarak gösterilir), boş olmayan bir köşe veya düğüm kümesi V ve bir dizi kenar E'den oluşur.
Example - Bir Grafiğin $ G = (V, E) $ olduğunu düşünelim, burada $ V = \ lbrace a, b, c, d \ rbrace $ ve $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $
Degree of a Vertex - Bir G grafiğinin V tepe noktasının derecesi (derece (V) ile gösterilir), tepe V ile gelen kenarların sayısıdır.
| Köşe | Derece | Tek çift |
|---|---|---|
| a | 2 | hatta |
| b | 2 | hatta |
| c | 3 | garip |
| d | 1 | garip |
Even and Odd Vertex - Bir tepe noktasının derecesi çift ise, tepe noktası çift tepe noktası olarak adlandırılır ve bir tepe noktası tuhafsa, tepe noktası tek bir tepe noktası olarak adlandırılır.
Degree of a Graph- Bir grafiğin derecesi, o grafiğin en büyük köşe derecesidir. Yukarıdaki grafik için grafiğin derecesi 3'tür.
The Handshaking Lemma - Bir grafikte, tüm köşelerin tüm derecelerinin toplamı, kenar sayısının iki katına eşittir.
Grafik Türleri
Aşağıdaki bölümde öğreneceğimiz farklı grafik türleri vardır.
Boş Grafik
Boş grafiğin kenarları yoktur. $ N $ köşelerinin boş grafiği $ N_n $ ile gösterilir
Basit Grafik
Grafik yönlendirilmemişse ve herhangi bir döngü veya birden çok kenar içermiyorsa, grafiğe basit grafik / katı grafik denir.
Çoklu Grafik
Bir grafikte aynı köşe seti arasında birden fazla kenara izin veriliyorsa, buna Multigraph denir. Başka bir deyişle, en az bir döngüye veya çok sayıda kenara sahip bir grafiktir.
Yönlendirilmiş ve Yönlendirilmemiş Grafik
Kenar kümesi sıralı köşe çiftinden yapılmışsa, bir $ G = (V, E) $ grafiği, yönlendirilmiş grafik olarak adlandırılır ve kenar kümesi sırasız köşe çiftinden yapılmışsa bir grafik yönsüz olarak adlandırılır.
Bağlı ve Bağlantısız Grafik
Grafiğin herhangi iki köşesi bir yolla bağlıysa, bir grafik bağlanır; grafiğin en az iki köşesi bir yolla bağlı değilse grafiğin bağlantısı kesilir. Bir G grafiğinin bağlantısı kesilirse, o zaman her maksimum bağlı $ G $ alt grafiğine $ G $ grafiğinin bağlı bileşeni denir.
Normal Grafik
Grafiğin tüm köşeleri aynı dereceye sahipse bir grafik normaldir. $ R $ derecesindeki normal bir G grafiğinde, $ G $ 'ın her köşesinin derecesi r'dir.
Tam Grafik
Her iki köşe çifti tam olarak bir kenarla birleştirilirse, grafiğe tam grafik denir. N köşeli tam grafik $ K_n $ ile gösterilir
Döngü Grafiği
Bir grafik tek bir döngüden oluşuyorsa buna döngü grafiği denir. N köşeli döngü grafiği $ C_n $ ile gösterilir
İkili Grafik
Bir G grafiğinin köşe kümesi iki ayrık kümeye, $ V_1 $ ve $ V_2 $ olarak bölünebiliyorsa, grafikteki her bir kenar $ V_1 $ 'da bir tepe noktasını $ V_2 $' da bir tepe noktasına birleştirecek şekilde, ve G'de $ V_1 $'daki iki köşeyi veya $ V_2 $'daki iki köşeyi birbirine bağlayan kenarlar yoktur, ardından $ G $ grafiğine iki parçalı grafik denir.
Tam İki Taraflı Grafik
Tam bir iki parçalı grafik, birinci kümedeki her bir tepe noktasının ikinci kümedeki her bir tepe noktasına birleştirildiği iki parçalı bir grafiktir. Tam iki parçalı grafik $ K_ {x, y} $ ile gösterilir ve burada $ G $ grafiği, ilk kümede $ x $ köşeleri ve ikinci kümede $ y $ köşelerini içerir.
Grafiklerin Gösterimi
Bir grafiği göstermenin başlıca iki yolu vardır -
- Bitişiklik Matrisi
- Komşuluk Listesi
Bitişiklik Matrisi
Bir Bitişiklik Matrisi $ A [V] [V] $, $ V \ times V $ boyutunda bir 2D dizidir; burada $ V $, yönsüz bir grafikteki köşe sayısıdır. $ V_x $ ile $ V_y $ arasında bir kenar varsa, o zaman $ A [V_x] [V_y] = 1 $ ve $ A [V_y] [V_x] = 1 $ değeri, aksi takdirde değer sıfır olacaktır. Yönlendirilmiş bir grafik için, $ V_x $ ile $ V_y $ arasında bir kenar varsa, o zaman $ A [V_x] [V_y] = 1 $ 'ın değeri, aksi takdirde değer sıfır olacaktır.
Adjacency Matrix of an Undirected Graph
Aşağıdaki yönsüz grafiği ele alalım ve bitişik matrisini oluşturalım -
Yukarıdaki yönsüz grafiğin bitişik matrisi şöyle olacaktır -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
c |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
Adjacency Matrix of a Directed Graph
Aşağıdaki yönlendirilmiş grafiği ele alalım ve bitişik matrisini oluşturalım -
Yukarıda yönlendirilen grafiğin bitişik matrisi -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
0 |
0 |
1 |
0 |
c |
0 |
0 |
0 |
1 |
d |
0 |
0 |
0 |
0 |
Komşuluk Listesi
Bitişiklik listesinde, G grafiğini $ V $ sayıda köşe noktasıyla temsil etmek için, bağlı listelerin $ (A [V]) $ dizisi kullanılır. $ A [V_x] $ girdisi, $ Vx-th $ tepe noktasına bitişik bağlantılı köşelerin listesini temsil eder. Yönlendirilmemiş grafiğin bitişiklik listesi aşağıdaki şekilde gösterildiği gibidir -
Düzlemsel ve Düzlemsel olmayan grafik
Planar graph- Bir $ G $ grafiği, herhangi bir kenarları kesişmeden bir düzlemde çizilebiliyorsa, düzlemsel grafik olarak adlandırılır. Düzlemde kenar geçişi olmadan grafik çizersek buna grafiğin düzleme gömülmesi denir.
Non-planar graph - Grafik kenarları kesişmeyen bir düzlemde çizilemeyen bir grafik düzlemsel değildir.
İzomorfizm
İki G ve H grafiği aynı şekilde bağlanmış aynı sayıda köşe içeriyorsa, bunlara izomorfik grafikler denir ($ G \ cong H $ ile gösterilir).
İzomorfizmi kontrol etmek, izomorfizme göre daha kolaydır. Aşağıdaki koşullardan herhangi biri meydana gelirse, iki grafik izomorfik değildir -
- Bağlı bileşenlerin sayısı farklı
- Köşe-set kardinaliteleri farklıdır
- Kenar set kardinaliteleri farklıdır
- Derece dizileri farklıdır
Misal
Aşağıdaki grafikler izomorfiktir -
Homomorfizm
$ G $ grafiğinden $ H $ grafiğine bir homomorfizm bir eşlemedir (iki amaçlı bir eşleme olamaz) $ h: G \ rightarrow H $ öyle ki - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ E (H) $ içinde. $ G $ grafiğinin bitişik köşelerini $ H $ grafiğinin bitişik köşelerine eşler.
Homomorfizmlerin Özellikleri
Bir homomorfizm, bijektif bir haritalama ise bir izomorfizmdir.
Homomorfizm her zaman bir grafiğin kenarlarını ve bağlantılılığını korur.
Homomorfizmlerin bileşimleri de homomorfizmlerdir.
Başka bir grafiğin herhangi bir homomorfik grafiğinin olup olmadığını bulmak NP-tamamlanmış bir problemdir.
Euler Grafikleri
$ G $ grafiğinin her kenarını içeren kapalı bir iz varsa, bağlı bir grafik $ G $ bir Euler grafiği olarak adlandırılır. Euler yolu, bir grafiğin her kenarını tam olarak bir kez kullanan bir yoldur. Bir Euler yolu farklı köşelerde başlar ve biter.
Euler devresi, bir grafiğin her kenarını tam olarak bir kez kullanan bir devredir. Bir Euler devresi her zaman aynı tepe noktasında başlar ve biter. Bağlı bir grafik $ G $ bir Euler grafiğidir ancak ve ancak $ G $ 'ın tüm köşeleri eşit derecedeyse ve bağlı bir grafik $ G $ Eulerian ise ancak ve ancak kenar kümesi döngülere ayrıştırılabiliyorsa.
Yukarıdaki grafik $ "a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 şeklinde bir Euler grafiğidir \: g ”$ grafiğin tüm kenarlarını kapsar.
Hamilton Grafikleri
$ G $ 'ın her köşesini içeren bir döngü varsa ve döngü Hamilton döngüsü olarak adlandırılırsa, bağlantılı bir grafik $ G $ Hamilton grafiği olarak adlandırılır. Hamiltonian yürüyüş grafiği $ G $, her bir tepe noktasından tam olarak bir kez geçen bir yürüyüştür.
$ G $ n köşeli basit bir grafikse, burada $ n \ geq 3 $ Eğer $ deg (v) \ geq \ frac {n} {2} $ her köşe için $ v $ için, $ G $ grafiği Hamilton grafiği. Bu denirDirac's Theorem.
$ G $, $ n $ köşeleri olan basit bir grafikse, burada $ n \ geq 2 $ eğer $ deg (x) + deg (y) \ geq n $ her bitişik olmayan köşe noktası çifti için x ve y, o zaman $ G $ grafiği Hamilton grafiğidir. Bu denirOre's theorem.
