Gayri resmi olarak, bir grafik, oklarla veya oklar olmadan bu noktaları birbirine bağlayan bir dizi nokta ve çizgi olarak düşünülebilir.
Matematiksel bir disiplin olarak çizge teorisinin ilk çalışması, Köningsberg köprüleri problemini ele alan Euler'in makalesi (1736) olarak kabul edilir. Euler, yedi şehir köprüsünü atlayıp, her köprüyü tam olarak bir kez geçerek başlangıç noktasına dönmenin imkansız olduğunu gösterdi. Grafik teorisi bir sonraki ivmesini neredeyse 100 yıl sonra elektrik ağları, kristalografi, organik kimya ve diğer bilimlerdeki araştırmaların gelişmesiyle aldı.
Farkında olmadan sürekli grafiklerle karşılaşıyoruz. Örneğin bir grafik metro hatlarının bir diyagramıdır. Üzerindeki noktalar istasyonları, çizgiler ise tren rotalarını temsil ediyor. Atalarımızı araştırıp uzak bir ataya kadar takip ederek sözde bir aile ağacı oluşturuyoruz. Ve bu ağaç bir grafiktir.
Grafikler nesneler arasındaki ilişkileri tanımlamanın uygun bir yolu olarak hizmet eder. Daha önce sonlu ikili ilişkileri görsel olarak temsil etmenin bir yolu olarak grafikleri kullanmıştık.
Ancak grafik yalnızca örnek olarak kullanılmaz. Örneğin, yerleşim alanları arasındaki yol ağını gösteren bir grafiği göz önünde bulundurarak, A noktasından B noktasına kadar olan rotayı belirleyebilirsiniz. Bu tür birkaç rota varsa, bir anlamda en uygun olanı seçmek istersiniz, örneğin en kısa veya en güvenli olanıdır. Seçim problemini çözmek için grafikler üzerinde belirli hesaplamaların yapılması gerekmektedir. Bu tür problemleri çözerken cebirsel tekniklerin kullanılması uygundur ve grafik kavramının resmileştirilmesi gerekir.
Grafik teorisi yöntemleri ayrık matematikte yaygın olarak kullanılmaktadır. Çeşitli ayrık dönüştürücüleri analiz ederken ve sentezlerken onlarsız yapmak imkansızdır: bilgisayarların işlevsel blokları, yazılım paketleri vb.
Şu anda, grafik teorisi birçok materyali kapsıyor ve aktif olarak gelişiyor. Bunu sunarken kendimizi sonuçların yalnızca bir kısmıyla sınırlayacağız ve asıl vurguyu biçimsel diller teorisinde kullanılan bazı yaygın grafik analiz algoritmalarının açıklamasına ve gerekçelerine vereceğiz.
Temel tanımlar
Örneklerde daha önce de belirtildiği gibi grafikler, belirli nesneler arasındaki bağlantıları "görselleştirmenin" bir yoludur. Bu bağlantılar, örneğin bir aile ağacında olduğu gibi "yönlendirilmiş" veya "yönsüz" (iki yönlü bir ağ) olabilir. yollar). Buna göre çizge teorisinde iki ana tür çizge vardır: yönlendirilmiş (veya yönlendirilmiş) ve yönsüz.
Sunum yöntemleri
Şu ana kadar yönlendirilmiş ve yönlendirilmemiş grafikleri çizimlerle göstererek tanımladık. Tanımı takip ederek bir grafiği bir çift küme olarak tanımlayabilirsiniz, ancak bu yöntem oldukça hantaldır ve teorik olarak ilgi çekicidir. Grafiklerin özelliklerini analiz etmek için algoritmik yaklaşımların geliştirilmesi, bilgisayar kullanmak da dahil olmak üzere, pratik hesaplamalar için daha uygun olan grafikleri tanımlamanın başka yollarını gerektirir. Grafikleri temsil etmenin en yaygın üç yoluna bakalım.
Ağaçlar
Tanım 5.5. Yönsüz bir ağaç, bağlantılı ve döngüsel olmayan, yönlendirilmemiş bir grafiktir. Tanım 5.6. Yönlendirilmiş bir ağaç, herhangi bir tepe noktasının yarım derecesinin 1'den büyük olmadığı ve yarım derecesi 0 olan, yönlendirilmiş ağacın kökü adı verilen tam olarak bir tepe noktasının bulunduğu, kontur olmayan yönlendirilmiş bir grafiktir.
En az ağırlığı kapsayan ağaç
Aşağıdaki problem grafik teorisinde Steiner problemi olarak bilinir: Bir düzlemde n nokta verilmiştir; bunları, bölümlerin toplam uzunluğu minimum olacak şekilde düz bölümlerle bağlamanız gerekir.
Grafik köşelerini sistematik olarak geçme yöntemleri
Çizge teorisindeki önemli problemler hem yönlendirilmemiş hem de yönlendirilmiş çizgelerin global analizindeki sorunlardır. Bu görevler, örneğin döngüleri veya konturları bulma görevini, köşe çiftleri arasındaki yolların uzunluklarını hesaplamayı, belirli özelliklere sahip yolları listelemeyi vb. içerir. Küresel grafik analizi, bir örneği yönlendirilmiş bir grafiğin sabit bir köşesinin öncülleri ve ardılları kümelerini belirleme sorunu olan yerel analizden ayırt edilmelidir.
Ağırlıklı yönlendirilmiş grafiklerde yol problemi
Grafik izomorfizmi
Yönlendirilmiş bir grafik (V, E) için, yayların E kümesi, köşeler kümesinde tanımlanan ikili doğrudan ulaşılabilirlik ilişkisinin bir grafiği olarak düşünülebilir. Yönlendirilmemiş bir grafikte (V, E), kenarlardan oluşan E kümesi, sırasız çiftlerin kümesidir. Her sırasız (u, v) ∈ E çifti için, u ve v köşelerinin simetrik bir ikili ilişki p ile bağlı olduğunu varsayabiliriz; (u, v) ∈ р ve (v, u) ∈ р.
Topolojik sıralama
Tanım 5.17. Yönlendirilmiş bir ağ (veya basitçe bir ağ), kontursuz yönlendirilmiş bir grafiktir*. Ağ kontursuz bir grafik olduğundan, ağın dış derecesi sıfır olan köşelerinin (düğümlerinin) yanı sıra sıfır dereceli köşelerinin (düğümleri) olduğu gösterilebilir. Bunlardan ilkine ağın havuzları veya çıktıları, ikincisine ise ağın kaynakları veya girişleri denir.
Siklomatik unsurları
Yönlendirilmemiş bir grafikte derinlik öncelikli arama algoritmasını tartışırken, grafiğin sözde temel döngülerini arama sorunu dikkate alındı. Bu durumda, bir temel döngü, tam olarak bir ters kenar içeren bir döngü olarak anlaşıldı ve yönsüz bir grafiğin tüm kenarlarının keyfi olarak bölünmesi durumunda temel döngüler ile ters kenarlar arasında bire bir yazışma oluşturuldu; ağaçlar (orijinal grafiğin bazı maksimum kenar ormanlarını oluşturur) ve tersidir ve genel durumda bu bölüm, derinlik öncelikli arama algoritmasından tamamen bağımsız olarak belirlenebilir. Derinlik öncelikli arama böyle bir bölümü uygulamanın yollarından yalnızca biridir.
Grafik teorisi, bilgisayar bilimi ve programlama, ekonomi, lojistik ve kimyada kullanılan bir matematik dalıdır.
Grafik nedir
Grafik diyagramlar genellikle sistemlerin yapısını tanımlamak için kullanılır. İçlerindeki öğeler daireler, noktalar, kareler vb. ile temsil edilir ve öğeler arasındaki bağlantılar çizgiler veya oklarla temsil edilir. Bu durumda ne elemanların nasıl tasvir edildiği ne de çizgilerin uzunluğu veya şekli önemli değildir; yalnızca hangi elemanların birbirine bağlandığı önemlidir. Yani, bir grafik (A, M) formunun bir çiftidir; burada A, sonlu bir köşe kümesidir ve M, bazı köşeleri birbirine bağlayan bir dizi kenardır - çizgiler.
Grafik teorisinin temel kavramları
Yönlendirilmiş bir grafik veya digraf (aşağıdaki şekle bakın), yay adı verilen ve oklarla gösterilen yönlendirilmiş kenarlara sahiptir. Bir yay, bağladığı sıralı bir köşe çifti, bir başlangıç ve bir bitiş ile gösterilebilir.
Yönsüz bir grafiğin (aşağıdaki şekle bakın), yönü olmayan çizgiler olarak çizilen kenarları vardır. Buna göre bir kenarla bağlanan köşe çifti sırasızdır. Bu köşelerin her ikisi de kenarın uçlarıdır.
Eğer a ve b köşeleri grafiğin bir kenarının uçları (veya bir yayın başlangıcı ve sonu) ise, o zaman a ve b köşelerinin bu kenara (yaya) geldiği söylenir ve kenar (yay) da a ve b köşelerine gelen olay. Eğer a ve b köşeleri bir kenarın uçları ise, o zaman bunlara (a ve b) bitişik denir.
Çoğu zaman, kenarları tek tip olan (yönlendirilmiş olsun veya olmasın) grafikleri dikkate alırız.
Kenarlar aynı başlangıç ve bitişe sahipse, bunlara çoklu kenarlar denir ve bunların mevcut olduğu grafiğe çoklu grafik denir.
Grafik teorisi aynı zamanda "döngü" kavramını da kullanır - dışarı çıkan ve aynı tepe noktasına giren bir kenar. Döngüleri olan bir grafa sözde grafik denir.
En yaygın olanı, birden fazla kenarı ve döngüsü olmayan yönlendirilmemiş grafiklerdir. Bu tür grafiklere sıradan denir. Birden fazla kenarları yoktur, dolayısıyla bir kenarı ve ona karşılık gelen köşe çiftini tanımlayabiliriz.
Digrafın her köşesi aşağıdakilerle karakterize edilir:
- Yarım derece sonuç. Bu, ondan çıkan yayların sayısıdır.
- Yarım derece yaklaşma. Bu, belirli bir tepe noktasına giren yayların sayısıdır.
Bir digrafın girişinin yarım derecelerinin toplamı ve sonucun yarım derecelerinin toplamı, grafiğin toplam yay sayısına eşittir.
Yönlendirilmemiş bir grafikte, her köşe, tepe noktasının derecesi ile karakterize edilir. Bu, bir tepe noktasına gelen kenarların sayısıdır. Grafiğin köşe noktalarının derecelerinin toplam toplamı kenar sayısının ikiyle çarpımıdır: her kenar ikiye eşit bir katkı sağlayacaktır.
Derecesi 0 olan bir köşeye izole edilmiş köşe adı verilir.
Asılı bir köşe, derecesi 1 olan bir köşedir.
Grafik teorisi, kenarları olmayan boş bir grafik olarak adlandırılır. Tam bir grafik, herhangi 2 köşenin bitişik olduğu sıradan bir grafiktir.
Ağırlıklı grafikler, köşelerine veya kenarlarına (yaylar) veya hem köşelerine hem de kenarlarına (yaylar) aynı anda belirli sayılar atanan grafiklerdir. Bunlara terazi denir. İkinci şekil, kenarları ağırlıklı olan yönlendirilmemiş bir grafiği göstermektedir.
Grafikler: izomorfizm
İzomorfizm kavramı matematikte kullanılır. Özellikle, grafik teorisi bunu şu şekilde tanımlar: iki U ve V grafiği, eğer bu grafiklerde köşe kümeleri arasında bir eşleşme varsa izomorfiktir: U grafiğindeki her 2 köşe, ancak ve ancak şu durumda bir kenarla bağlanır: grafik V aynı olanlar bir kenar köşesiyle bağlanır (farklı isimlere sahip olabilir). Aşağıdaki şekil, hem birinci hem de ikinci grafiklerde aynı renklerle renklendirilmiş köşeler arasında yukarıda açıklanan eşleşmenin mevcut olduğu iki izomorfik grafiği göstermektedir.
Yollar ve döngüler
Yönsüz veya yönlendirilmiş bir grafikteki yol, her bir sonrakinin bir öncekinin bittiği tepe noktasında başladığı bir kenar dizisidir. Basit bir yol, belki başlangıç ve bitiş hariç tüm köşelerin ve kenarların farklı olduğu yoldur. Bir digraftaki döngü, başlangıç ve bitiş köşeleri çakışan ve en az bir kenar içeren bir yoldur. Yönsüz bir grafikteki bir döngü, en az üç farklı kenar içeren bir yoldur. İkinci şekilde döngü örneğin (3, 1), (6, 3), (1, 6) yoludur.
Programlamada grafik teorisi, algoritmaların grafik diyagramlarını oluşturmak için kullanılır.
K. Berge'nin kitabı, Rusça'da grafik teorisi üzerine ilk kitaptır. Bu arada, son yıllarda hem matematikçiler hem de çok çeşitli disiplinlerin temsilcileri açısından teoriye olan ilgi keskin bir şekilde arttı. Bu, grafik teorisi yöntemlerinin elektrik devreleri teorisi, taşıma zincirleri teorisi, bilgi teorisi, sibernetik vb. alanlardaki sayısız problemi başarıyla çözmesiyle açıklanmaktadır.
Berge'nin kitabında grafik teorisi en temelden başlayarak sırayla sunuluyor. Okuyucunun bir miktar matematik kültürüne sahip olmasına rağmen oldukça mütevazı bir matematik bilgisine sahip olduğu varsayılmaktadır. Metinde çok sayıda ve çoğunlukla komik örnekler yer alıyor. Kitap, grafik teorisinin ilk çalışması için kullanılabilir. Profesyonel matematikçiler de bunda pek çok ilginç şey bulacaklar.
Bir Eulerian döngüsünü doğrudan tanımlamak için bir algoritma.
[Fleury]. Tüm köşeleri eşit dereceye sahip olan bağlantılı bir çoklu grafik G'yi ele alalım ve inşaat süreci sırasında yörüngenin önceden çizilmiş kısmında düzeltmelere başvurmadan onu tek vuruşla çizmeye çalışacağız. Aşağıdaki kurala uymanız yeterlidir:
1 Rastgele bir a noktasından çıkıyoruz; Geçilen her kenarın üzerinden geçiyoruz.
2 Asla böyle bir kenar boyunca gitmeyiz ve söz konusu şu anda bir kıstaktır (yani kaldırıldığında, çaprazlanmamış kenarlardan oluşan grafik, her biri en az bir kenara sahip iki bağlantılı bileşene bölünür),
Bu kuralı takip ederek her zaman uygun bir konumda olacağız, çünkü x = a'da olduğumuzda, grafiğin (çapraz olmayan kenarlardan oluşan) tek dereceli iki köşesi vardır: x ve a; izole edilmiş köşeler atılırsa, Teorem 1'e göre x'ten başlayan bir Euler zincirine sahip bağlantılı bir grafik kalır.
İçerik
giriiş
Bölüm 1. Temel tanımlar
Kümeler ve çok değerli eşlemeler
Grafik. Yollar ve konturlar
Devreler ve döngüler
Bölüm 2. Yarı-düzenliliğin ön çalışması
Grafikle tanımlanan yarı sıra
Endüktif grafik ve bazlar
Bölüm 3. Sıralı fonksiyon ve fonksiyon
Sonsuz bir grafik için Grundy
Sonsuz grafiklerle ilgili genel hususlar
Sıra işlevi
Grundy fonksiyonları
Grafikler üzerinde işlemler
Bölüm 4. Grafik teorisinin temel sayıları
Siklomatik sayı
Kromatik sayı
Dahili stabilite numarası
Harici stabilite numarası
Bölüm 5. Grafik Çekirdekleri
Varlık ve teklik teoremleri
Grundy fonksiyonlarına uygulama
Bölüm 6. Grafik Oyunları
Oyun Nim
Oyunun genel tanımı (tüm bilgilerle birlikte)
Stratejiler
Bölüm 7. En Kısa Yol Problemi
Aşamalara göre süreçler Bazı genellemeler
Bölüm 8. Taşıma ağları
Maksimum Akış Sorunu En Az Akış Sorunu
Ayar Değeri Uyumlu Akış Problemi
Sonsuz ulaşım ağları
Bölüm 9. Yarı kuvvetlerle ilgili teorem
Yarı derece giden ve giren
Bölüm 10. Basit bir grafiği eşleştirme
Maksimum eşleştirme sorunu
Basit grafik eksikliği
Macar algoritması
Sonsuz duruma genelleme
Matris teorisine uygulama
Bölüm 11. Faktörler
Hamilton yolları ve Hamilton konturları
Bir faktör bulma
Verilen yarım derecelere sahip kısmi bir grafiği bulma
Bölüm 12. Grafik Merkezleri
Merkezler
Yarıçap
Bölüm 13. Güçlü bağlantılı bir grafiğin çapı
Döngüler olmadan güçlü bağlantılı grafiklerin genel özellikleri
Çap
Bölüm 14. Grafik Komşuluk Matrisi
Geleneksel matris işlemlerinin uygulanması
Sayma sorunları
Lider sorunu
Boolean İşlemlerini Kullanma
Bölüm 15. Olay matrisleri
Tamamen tek modüler matrisler
Tamamen tek modüler sistemler
Siklomatik matrisler
Bölüm 16. Ağaçlar ve atalardan kalma ağaçlar
Ağaçlar
Analitik araştırma
Büyük ağaçlar
Bölüm 17. Euler'in sorunu
Euler, Euler konturlarını döndürür
Bölüm 18. Rastgele bir grafiği eşleştirme
Alternatif Devre Teorisi
Verilen köşe derecelerine sahip kısmi bir grafiği bulma
Mükemmel eşleştirme
Dahili stabilite numarasına başvuru
Bölüm 19. Faktoroidler
Hamilton döngüleri ve faktöroidler
Faktoroidin varlığı için gerekli ve yeterli koşul
Bölüm 20. Grafik Bağlantısı
Eklem noktaları
Eklemsiz grafikler
h bağlantılı grafikler
Bölüm 21. Düzlemsel grafikler
Temel özellikler
Genelleme
İlaveler
I. Genel teori dışında, oyunlar
II. Taşıma görevleri hakkında
III. Ulaştırma ağlarında potansiyel kavramların kullanımı üzerine
IV. Çözülmemiş problemler ve kanıtlanmamış varsayımlar
V. Saymanın bazı temel ilkeleri üzerine (J. Riguet)
VI. Rusça çeviriye eklemeler (A.A. Zykov ve G.I. Kozhukhin)
Edebiyat
Graf teorisi ve C. Berge'nin kitabı (Rusça tercümenin sonsözü)
Karakter dizini
Ad dizini
Konu dizini.
E-kitabı uygun bir formatta ücretsiz indirin, izleyin ve okuyun:
Graf Teorisi ve Uygulamaları, Berge K. - fileskachat.com kitabını indirin, hızlı ve ücretsiz indirin.
Grafik teorisi, ayrı öğeler (köşeler) olarak temsil edilen nesneleri ve bunlar arasındaki bağlantıları (yaylar, kenarlar) inceleyen ayrık matematiğin bir dalıdır.
Graf teorisi, ünlü matematikçinin 1736 yılında Königsberg köprüleri probleminin çözümünden kaynaklanmaktadır. Leonard Euler(1707-1783: İsviçre'de doğdu, Rusya'da yaşadı ve çalıştı).
Königsberg köprüleriyle ilgili sorun.
Pregal Nehri üzerindeki Prusya'nın Königsberg kasabasında yedi köprü var. Her köprüden tam olarak bir kez geçen ve aynı yerde başlayıp aynı yerde biten bir yürüyüş rotası bulmak mümkün müdür?
Aynı tepe noktasında başlayıp biten ve grafiğin tüm kenarları boyunca tam olarak bir kez geçen bir rotanın bulunduğu grafa denir.Euler grafiği.
İstenilen rotanın geçtiği köşelerin (belki tekrarlanan) dizisine ve rotanın kendisine denir.Euler döngüsü .
Üç ev ve üç kuyu sorunu.
Bir uçakta bir şekilde konumlandırılmış üç ev ve üç kuyu var. Yolların kesişmemesi için her evden her kuyuya bir yol çizin. Bu sorun 1930 yılında Kuratovsky (1896 - 1979) tarafından çözülmüştür (çözümünün olmadığı gösterilmiştir).
Dört renk problemi. Bir düzlemin kesişmeyen alanlara bölünmesine ne ad verilir? kartla. Harita alanları ortak bir sınıra sahipse bitişik olarak adlandırılır. Görev, haritayı iki bitişik alanın aynı renge boyanmayacağı şekilde renklendirmektir. 19. yüzyılın sonlarından beri bunun için dört rengin yeterli olduğu hipotezi biliniyor. Hipotez henüz kanıtlanmadı.
Yayınlanan çözümün özü, dört renk teoremine yönelik çok sayıda ancak sonlu sayıda (yaklaşık 2000) potansiyel karşı örnek türünü sıralamak ve tek bir durumun bile karşı örnek olmadığını göstermektir. Bu arama program tarafından yaklaşık bin saatlik süper bilgisayar çalışmasıyla tamamlandı.
Ortaya çıkan çözümü "manuel olarak" kontrol etmek imkansızdır - numaralandırmanın kapsamı insan yeteneklerinin kapsamı dışındadır. Pek çok matematikçi şu soruyu gündeme getiriyor: Böyle bir "program kanıtı" geçerli bir kanıt olarak kabul edilebilir mi? Sonuçta programda hatalar olabilir...
Bu nedenle yalnızca yazarların programlama becerilerine güvenebilir ve her şeyi doğru yaptıklarına inanabiliriz.
Tanım 7.1. Saymak G= G(V, e) iki sonlu kümenin koleksiyonudur: V – denir birçok köşe ve V'den gelen eleman çiftlerinden oluşan E kümesi, yani. EÍV'V, çağrıldı birçok kenar, eğer çiftler sırasızsa veya birçok yay, eğer çiftler sıralanmışsa.
İlk durumda, grafik G(V, e) isminde yönsüz, ikincisinde – odaklı.
ÖRNEK. Bir dizi köşesi V = (a,b,c) ve bir dizi kenarı E =((a, b), (b, c)) olan bir grafik
ÖRNEK. V = (a,b,c,d,e) ve E = ((a, b), (a, e), (b, e), (b, d), (b, c) olan bir grafik, (c, d)),
Eğer e=(v 1 ,v 2), еОЕ ise kenarın e olduğunu söylerler. bağlanır v 1 ve v 2 köşeleri.
İki köşe v 1, v 2 olarak adlandırılır bitişik, eğer onları birbirine bağlayan bir kenar varsa. Bu durumda köşelerin her birine denir. olay karşılık gelen kenar .
İki farklı kaburga bitişik ortak bir köşeye sahiplerse. Bu durumda kenarların her birine denir. tesadüfi karşılık gelen köşe .
Grafik köşe sayısı G hadi belirtelim v ve kenar sayısı e:
.
Grafiklerin geometrik gösterimi aşağıdaki gibidir:
1) grafiğin tepe noktası uzayda (düzlemde) bir noktadır;
2) yönlendirilmemiş bir grafiğin kenarı - bir parça;
3) yönlendirilmiş bir grafiğin yayı – yönlendirilmiş bir bölüm.
Tanım 7.2. Eğer kenarda e=(v 1 ,v 2) v 1 =v 2 oluşursa, e kenarına çağrılır. döngü. Bir grafik döngülere izin veriyorsa buna denir. döngüler içeren grafik veya sahte yazı .
Bir graf iki köşe arasında birden fazla kenara izin veriyorsa buna denir. çoklu grafik .
Bir grafiğin her köşesi ve/veya kenarı etiketlenmişse, böyle bir grafik denir işaretlenmiş (veya yüklü ). İşaret olarak genellikle harfler veya tam sayılar kullanılır.
Tanım 7.3. Grafik G (V , e ) isminde alt yazı (veya parça ) grafik G(V,e), Eğer V V, e e. Eğer V = V, O G isminde kapsayan alt grafik G.
Örnek 7 . 1 . Yönsüz bir grafik verildiğinde.
Tanım 7.4. Grafik denir tamamlamak , Eğer herhangi iki köşesi bir kenarla birbirine bağlanmıştır. Grafiği şununla tamamla: N köşeler şu şekilde gösterilir: k N .
K sayılır 2 , İLE 3, İLE 4 ve K 5 .
Tanım 7.5. Grafik G=G(V, e) denir iki çenekli , Eğer V ayrık kümelerin bir birleşimi olarak temsil edilebilir, diyelim ki V=AB, yani her kenar şu şekle sahiptir ( v Ben , v J), Nerede v Ben A Ve v J B.
Her kenar, A'daki bir köşeyi B'deki bir köşeye bağlar, ancak A'dan iki köşe veya B'den iki köşe birbirine bağlı değildir.
İki parçalı bir grafik denir tam dikotiledon saymak k M , N, Eğer A içerir M zirveler, B içerir N köşeler ve her biri için v Ben A, v J B sahibiz ( v Ben , v J)e.
Böylece herkes için v Ben A, Ve v J B onları birbirine bağlayan bir kenar var.
K 12 K 23 K 22 K 33
Örnek 7 . 2 . Tam iki parçalı bir grafik oluşturun k 2.4 ve grafiğin tamamı k 4 .
Birim grafiğiNboyutlu küpİÇİNDE N .
Grafiğin köşeleri n boyutlu ikili kümelerdir. Kenarlar, bir koordinatta farklı olan köşeleri birbirine bağlar.
Örnek: 
Grafikler eğlenceli, ödüllendirici ve korkutucu bir konudur. Grafik Teorisi - "Öğrencinin Korkusu". Grafik algoritmaları, onları keşfeden insanların muhteşem zekalarıdır.
Grafik nedir? Okuyucularım için bu soruyu yanıtlamak amacıyla konuyu biraz farklı anlatacağım.
Grafik bir nesneler kümesidir.
Çoğu problemde bunlar aynı türden nesnelerdir. (Birçok şehir, ya da birçok ev, ya da birçok insan ya da aynı türden birçok başka şey)
Böyle bir kümeyle ilgili sorunları çözmek için bu kümedeki her nesneyi bir şey olarak belirlemeniz gerekir. Genel olarak bu şeye grafiğin köşeleri denilmesi kabul edilir.
Grafikleri ve temel tanımları resimlerle anlatmak uygun olduğundan bu sayfayı okuyabilmek için resimlere yer verilmesi gerekmektedir.
Daha önce de yazdığım gibi, grafik bir nesneler kümesidir. Bu nesneler genellikle aynı türdendir. Örnek vermenin en kolay yolu şehirlerdedir. Her birimiz şehrin ne olduğunu ve yolun ne olduğunu biliyoruz. Her birimiz şehre giden yolların olabileceğini veya olmayabileceğini biliyoruz. Genel olarak herhangi bir nesne kümesi bir grafik olarak nitelendirilebilir.
Grafiğin şehirler hakkında konuşursak, şehirler arasında yollar yapılabilir veya bir yerlerde yıkılabilir, inşa edilmeyebilir veya şehir genel olarak bir ada üzerinde yer alır, köprü yoktur ve sadece asfalt yollar ilgi çekicidir. . Böyle bir şehre giden yol olmamasına rağmen bu şehir, analiz edilen birçok nesnenin arasına dahil edilebilir ve tüm nesneler bir arada ele alındığında bir nesne koleksiyonu veya daha basit bir ifadeyle bir grafik oluşturur.
Elbette ders kitaplarını okudunuz ve bu G(V,E) gösterimini veya buna benzer bir şeyi gördünüz. Yani V, tüm nesneler kümesinden bir nesnedir. Bizim durumumuzda nesneler kümesi şehirlerdir, dolayısıyla V belirli bir şehirdir. Nesnelerin mutlaka şehirler olması gerekmediğinden ve nesne kelimesi kafa karıştırıcı olabileceğinden, kümedeki böyle bir nesneye nokta, nokta veya başka bir şey denilebilir, ancak çoğu zaman buna grafiğin tepe noktası denir ve harfle gösterilir. V.
Programlamada bu genellikle iki boyutlu bir dizinin bir sütunu veya satırıdır; burada diziye bitişiklik matrisi veya olay matrisi denir.
Literatürde, internette ve genel olarak grafiklerle ilgili bir şeyler yazılan her yerde yay, kenar gibi kavramlarla karşılaşırsınız. Bu şekil grafiğin kenarlarını göstermektedir. Onlar. bunlar üç kenar E1, E2 ve E3'tür.
Yay ve kenar, kenarın çift yönlü bir bağlantı olması bakımından farklılık gösterir. İstedi, komşusuna gitti, istedi, komşusundan döndü. Çok net değilse bir ev, bir hava alanı, uçan bir uçak ve bir paraşütçü hayal edebilirsiniz. Bir paraşütçü evinden hava alanına gidebilir, ancak hava alanına vardığında şanslı paraşütünü evde unuttuğunu hatırlar ve ardından eve döner ve paraşütü alır. — İleri geri yürünebilen yola kenar denir.
Eğer bir paraşütçü uçaktaysa ve uçaktan atlarsa, ancak paraşütçü şanslı paraşütünü uçakta takmayı unutursa, paraşütçü unuttuğunu geri alabilecek mi? Yalnızca tek yönde giden yola yay denir. Genellikle bir kenarın iki köşeyi birleştirdiğini ve bir yayın bir köşeden diğerine gittiğini söyleriz.
Bu şekilde grafikte yalnızca yaylar var. Erişilebilir yön çok net olduğundan grafikteki yaylar oklarla gösterilmiştir. Bir grafik yalnızca bu tür yaylardan oluşuyorsa, böyle bir grafiğe yönlü denir.
 |
Sık sık bitişiklik ve olay kavramlarıyla karşılaşacaksınız. Şekilde bir noktaya giden iki kenar kırmızı renkle işaretlenmiştir. Yukarıda açıklanan köşeler gibi bu tür kenarlara da bitişik denir. |
Pek çok şey açıklanmadı, ancak bu bilgi birisine yardımcı olabilir.