Grafik (ayrık matematik) - Graph (discrete mathematics)

Altı köşesi ve yedi kenarı olan bir grafik.

Gelen matematik ve daha özel olarak grafik teorisi , bir grafik bir bir yapı tutarında olduğunu grubu nesnelerin bazıları çifti "ile ilgili" bir anlamda olduğu nesnelerin. Nesneler, köşeler (ayrıca düğümler veya noktalar olarak da adlandırılır ) adı verilen matematiksel soyutlamalara karşılık gelir ve ilgili köşe çiftlerinin her birine bir kenar ( bağlantı veya çizgi olarak da adlandırılır ) denir . Tipik olarak, bir grafik, kenarlar için çizgiler veya eğrilerle birleştirilen, köşeler için bir dizi nokta veya daire olarak şematik biçimde tasvir edilir . Grafikler, ayrık matematikte çalışmanın nesnelerinden biridir .

Kenarlar yönlendirilmiş veya yönlendirilmemiş olabilir. Noktaların bir partide insan temsil eder ve bunlar tokalaşın halinde bir kenar iki kişi arasındaki varsa herhangi bir kişi, çünkü, örneğin, daha sonra, bu grafik yönsüz bir kişinin el sallamak B sadece B ayrıca ile el A . Bir kişinin herhangi bir kenar Bunun aksine, A bir kişi B için tekabül A para borçlu B borçlu mutlaka ileri geri hareket değildir, çünkü, bu grafik, yöneliktir. İlk grafik türüne yönlendirilmemiş grafik , ikinci tür grafik ise yönlendirilmiş grafik olarak adlandırılır .

Grafikler, grafik teorisi tarafından incelenen temel konudur . "Grafik" sözcüğü bu anlamda ilk kez 1878'de JJ Sylvester tarafından matematik ve kimyasal yapı (kimya-grafik görüntü olarak adlandırdığı) arasındaki doğrudan ilişkide kullanılmıştır .

Tanımlar

Grafik teorisindeki tanımlar değişir. Aşağıdakiler, grafikleri ve ilgili matematiksel yapıları tanımlamanın daha temel yollarından bazılarıdır .

grafik

Üç köşesi ve üç kenarı olan bir grafik.

Bir grafik (bazen yönlendirilmiş bir grafikten ayırt etmek için yönlendirilmemiş grafik veya bir çoklu grafikten ayırt etmek için basit bir grafik olarak adlandırılır ), bir G = ( V , E ) çiftidir ; burada V , elemanları köşeler (tekil: tepe noktası) olarak adlandırılan bir kümedir , ve E , elemanları kenarlar (bazen bağlantılar veya çizgiler ) olarak adlandırılan bir çift köşelerdir .

{ x , y } kenarının x ve y köşelerine kenarın uç noktaları denir . Kenar söylenir birleştirme x ve y olmak ve olay ile x ve y . Bir köşe hiçbir kenara ait olmayabilir, bu durumda başka bir köşe ile birleştirilmemiştir.

Bir ufak matbaa birden kenarları uç noktaları aynı çifti sağlayan bir genellemedir. Bazı metinlerde çoklu grafiklere basitçe grafik denir.

Bazen grafiklerin, bir köşeyi kendisine birleştiren kenarlar olan döngüler içermesine izin verilir . Döngülere izin vermek için, kenarları iki küme yerine iki köşenin çoklu kümeleri olarak tanımlayarak yukarıdaki tanım değiştirilmelidir . Bu tür genelleştirilmiş grafiklere, döngülü grafikler veya basitçe döngülere izin verildiği bağlamdan açıkça anlaşıldığında grafikler denir .

Genel olarak, V köşeleri kümesinin sonlu olduğu varsayılır; bu, kenarlar kümesinin de sonlu olduğu anlamına gelir. Sonlu grafikler bazen dikkate alınır, ancak sonlu grafiklerdeki çoğu sonuç sonsuz duruma yayılmadığından veya oldukça farklı bir kanıta ihtiyaç duyduğundan , daha sıklıkla özel bir ikili ilişki türü olarak görülür .

Bir boş grafik bir olan bir grafiktir boş seti (ve böylece kenarların boş grubu) köşe. Sipariş bir Grafiğin köşeler onun sayıdır | V | . Boyutu grafik kenarlarının kendi sayıdır | E | . Ancak, algoritmaların hesaplama karmaşıklığını ifade etmek gibi bazı bağlamlarda, boyut | V | + | E | (aksi halde, boş olmayan bir grafiğin boyutu 0 olabilir). Derecesi ya da değerlik bir köşe buna olay olan kenarların sayısıdır; döngülü grafikler için bir döngü iki kez sayılır.

n dereceli bir grafikte, her köşenin maksimum derecesi n − 1'dir (veya döngülere izin veriliyorsa n ) ve maksimum kenar sayısı n ( n − 1)/2 (veya n ( n + 1)/ 2 döngülere izin verilirse).

Bir grafiğin kenarları , komşuluk ilişkisi adı verilen köşelerde simetrik bir ilişki tanımlar . Özel olarak, iki tepe noktaları x ve y olan bitişik ise { x , y } kenardır. Bir grafik tam olarak belirtilebilir komşuluk matrisi A'nın bir bir, ile, kare matris bir ij tepe bağlantı sayısını belirten i tepe için j . Basit bir grafik için, sırasıyla bağlantının kesilmesini veya bağlantısını gösterir (yani, bir kenar aynı köşede başlayıp bitemez). Kendinden döngülü grafikler, bazılarının veya tümünün pozitif bir tamsayıya eşit olmasıyla karakterize edilecek ve çoklu grafikler (köşeler arasında birden çok kenarlı), bazılarının veya tümünün pozitif bir tamsayıya eşit olmasıyla karakterize edilecektir . Yönlendirilmemiş grafikler simetrik bir komşuluk matrisine ( ) sahip olacaktır .

Yönlendirilmiş grafik

Üç köşesi ve dört yönlendirilmiş kenarı olan yönlendirilmiş bir grafik (çift ok, her yönde bir kenarı temsil eder).

Bir yönlendirilmiş grafik veya digraph kenarları yönlerde olduğu bir grafiktir.

Terimin sınırlı ancak çok yaygın bir anlamıyla, yönlendirilmiş bir grafik aşağıdakileri içeren bir çifttir :

  • Bir dizi bir köşe (ayrıca düğümleri veya noktalar );
  • Bir dizi arasında kenarları (ayrıca yönelik kenarlar , yönlendirilmiş bağlantılar , yönlendirilmiş çizgiler , oklar veya yay olan) çiftleri sipariş köşelerin (bir kenar iki ayrı köşe ile ilişkili olduğunu).

Belirsizliği önlemek için, bu tür bir nesneye tam olarak yönlendirilmiş basit bir grafik denilebilir .

Kenar olarak yönlendirilen için , köşe ve denir uç noktaları kenarının, kuyruk kenarının ve baş kenarının. Kenar söylenir birleştirme ve olmak ve olay ile ilgili ve ilgili . Bir grafikte bir köşe bulunabilir ve bir kenara ait olmayabilir. Kenar adlandırılır ters kenar bölgesinin . Yukarıdaki tanım kapsamında izin verilmeyen çoklu kenarlar , hem aynı kuyruk hem de aynı kafaya sahip iki veya daha fazla kenardır.

Birden çok kenara izin veren terimin daha genel bir anlamında, yönlendirilmiş bir grafik , aşağıdakileri içeren sıralı bir üçlüdür :

  • Bir dizi bir köşe (ayrıca düğümleri veya noktalar );
  • Bir dizi arasında kenarları (ayrıca yönelmiş kenarları , yönlendirilmiş bağlantılar , yönlendirilmiş çizgiler , oklar veya yayların );
  • , her kenarı sıralı bir köşe çiftine eşleyen bir geliş işlevi (yani, bir kenar iki farklı köşeyle ilişkilendirilir).

Belirsizliği önlemek için, bu tür bir nesneye tam olarak yönlendirilmiş çoklu grafik denilebilir .

Bir döngü , kendisi için bir tepe noktasını birleştiren bir kenardır. Döngüler olamaz üzerinde bir tepe noktasını birleştiren bir çevrim için iki tanım tanımlanan grafik yönettiği kendisi (a yönlendirilmiş basit grafik için) kenar veya (yönlendirilmiş bir ufak matbaa için) üzerinde doğrudan yer almaktadır içinde olmadığı . Bu nedenle, döngülere izin vermek için tanımların genişletilmesi gerekir. Yönlendirilmiş basit grafikler için tanımı değiştirilmelidir . Yönlendirilmiş çoklu grafikler için, tanımı olarak değiştirilmelidir . Belirsizliği önlemek için, bu tür nesnelere tam olarak sırasıyla döngülere izin veren yönlendirilmiş basit bir grafik ve döngülere izin veren yönlendirilmiş bir çoklu grafik (veya bir titreme ) adı verilebilir .

Döngüler izin veren bir yönlendirilmiş basit grafik kenarları a, homojen bir ilişki köşe üzerinde ~ denir bitişiklik ilişkisi içinde . Spesifik olarak, her kenar için , uç noktaları ve birbirine bitişik olduğu söylenir , bu da ~ ile gösterilir .

karışık grafik

Bir karışık grafik bazı kenarlar yönlendirilebilir ve biraz yönlendirilmeyen edilebilen bir grafiktir. Bu, sıralı olan üç G = ( V , E , A ) bir için karıştırılmış, basit grafik ve G = ( V , E , A , φ E , φ A ) bir için karıştırılmış ufak matbaa ile V , E (yönsüz kenarlar), A (yönlendirilmiş kenarlar), ϕ E ve ϕ A yukarıdaki gibi tanımlanır. Yönlü ve yönsüz grafikler özel durumlardır.

ağırlıklı grafik

On köşesi ve on iki kenarı olan ağırlıklı bir grafik.

Bir ağırlıklı grafik ya da şebeke bir sayı (ağırlık) her bir kenarına tahsis edildiği bir grafiktir. Bu tür ağırlıklar, eldeki soruna bağlı olarak örneğin maliyetleri, uzunlukları veya kapasiteleri temsil edebilir. Bu tür grafikler birçok bağlamda, örneğin gezgin satıcı problemi gibi en kısa yol problemlerinde ortaya çıkar .

Grafik türleri

Yönlendirilmiş grafik

Yönlendirilmiş bir grafiğin bir tanımı, ( x , y ) ve ( y , x ) öğelerinden en fazla birinin grafiğin kenarları olabileceği yönlendirilmiş bir grafik olmasıdır. Yani, yönsüz (basit) bir grafiğin yönlendirmesi olarak oluşturulabilen yönlendirilmiş bir grafiktir.

Bazı yazarlar "yönlendirilmiş grafik"i "yönlendirilmiş grafik" ile aynı anlamda kullanırlar. Bazı yazarlar, belirli bir yönsüz grafiğin veya çoklu grafiğin herhangi bir yönelimini ifade etmek için "yönelimli grafik" kullanır.

Normal grafik

Bir normal grafik her köşe komşu aynı sayıda, yani, her köşe aynı derecesine sahip olan bir grafiktir. Köşeleri k derece olan düzenli bir grafa k -düzenli graf veya k dereceli düzenli graf denir .

Grafiği tamamla

Beş köşesi ve on kenarı olan tam bir grafik. Her köşenin diğer her köşeye bir kenarı vardır.

Bir tam grafik köşelerin her bir çift, bir kenar ile birleştirilmiş olan bir grafiktir. Tam bir grafik tüm olası kenarları içerir.

sonlu grafik

Bir sonlu grafik tepe grubu ve kenar kümesi olduğu bir grafiktir sonlu kümeler . Aksi takdirde, sonsuz grafik olarak adlandırılır .

En yaygın olarak grafik teorisinde, tartışılan grafiklerin sonlu olduğu ima edilir. Grafikler sonsuz ise, bu genellikle özellikle belirtilir.

bağlı grafik

Bir yönsüz grafikte, köşelerin sırasız çifti { x , y } adlandırılır bağlı bir yol açması durumunda , x için y . Aksi takdirde, sırasız çifte bağlantısız denir .

Bir bağlı grafik grafikte köşe her düzensiz çift bağlı olduğu bir yönsüz grafiktir. Aksi takdirde, bağlantısız grafik olarak adlandırılır .

Bir yönlendirilmiş grafikte, köşe sıralı bir çift ( X , Y ) olarak adlandırılan bir kuvvetle bağlı bir yönlendirilmiş yol açar halinde gelen x için y . Aksi takdirde, sıralı ikili olarak isimlendirilir zayıf bağlı bir yönsüz yol açar halinde gelen x için y yönsüz kenarları ile yönelmiş kenarları tüm değiştirdikten sonra. Aksi takdirde, sıralı çifte bağlantısız denir .

Güçlü bağlantılı bir grafik , grafikteki her sıralı köşe çiftinin güçlü bir şekilde bağlı olduğu yönlendirilmiş bir grafiktir. Aksi takdirde, grafikteki sıralı her köşe çifti zayıf bağlantılıysa , buna zayıf bağlı grafik denir . Aksi takdirde, bağlantısız bir grafik olarak adlandırılır .

Bir k-köşe bağlantılı grafik veya k-kenar bağlantılı grafik , kaldırıldığında grafiğin bağlantısını kesen hiçbir k - 1 köşe (sırasıyla, kenarlar) kümesinin bulunmadığı bir grafiktir. Bir k -köşe bağlantılı graf genellikle basitçe k-bağlı graf olarak adlandırılır .

iki parçalı grafik

Bir bipartit grafik tepe grubu edilebileceği basit bir grafiktir paylaştırıldı iki takım halinde W ve X , böylece hiçbir iki tepe noktaları bu, B , ortak bir kenar ve bir, iki köşe X bir ortak uca paylaşır. Alternatif olarak, kromatik sayısı 2 olan bir grafiktir .

Bir de tam ikili grafik , tepe grubu, iki ayrık setleri, birliği W ve X , her köşe böylece, W her tepe için bitişik X , ancak içinde hiçbir kenarları vardır W veya X .

Yol grafiği

Bir yol grafiği ya da lineer bir grafiktir düzenin N ≥ 2 köşe bir düzen listelenen edilebildiği bir grafiktir v 1 , v 2 , ..., V n kenarlar öyle ki { v ı , v ı + 1 } burada i 1, 2, ..., = n 1. yol grafikleri tüm ama iki köşe derecesi 2 ve geri kalan iki köşe derecesi olduğu bağlı grafik olarak karakterize edilebilir: 1. bir yol grafiği olarak oluşur - alt grafiği başka bir grafiğin, o grafikteki bir yoldur .

düzlemsel grafik

Bir düzlemsel grafik olan köşeler ve kenarlar kenarlarının hiçbir iki kesişir bir düzlemde çizilebilir bir grafiktir.

döngü grafiği

n ≥ 3 dereceli bir döngü grafiği veya dairesel grafik , köşelerin v 1 , v 2 , …, v n sırasına göre listelenebildiği ve kenarların { v i , v i +1 } olduğu bir grafiktir. i = 1, 2, …, n − 1, artı kenar { v n , v 1 } . Döngü grafikleri, tüm köşelerin derecesinin 2 olduğu bağlantılı grafikler olarak karakterize edilebilir. Bir döngü grafiği, başka bir grafiğin alt grafiği olarak ortaya çıkarsa, o grafikteki bir döngü veya devredir.

Ağaç

Bir ağaç herhangi iki tanesi bir yönsüz grafiktir köşeler ile bağlanır tam bir yol , veya eşdeğer bir bağlı asiklik yönsüz grafik.

Bir orman , herhangi iki tepe noktasının en fazla bir yolla veya eşdeğerde döngüsel olmayan yönsüz bir grafikle veya eşdeğer olarak ayrık bir ağaç birleşimiyle bağlandığı yönsüz bir grafiktir .

Polytree

Bir çoklu ağaç (veya yönlendirilmiş ağaç veya yönlendirilmiş ağaç veya tek başına bağlı ağ ), altında yatan yönsüz grafiği bir ağaç olan bir yönlendirilmiş asiklik grafiktir (DAG).

Bir poliorman (veya yönlendirilmiş orman veya yönlendirilmiş orman ), altında yatan yönsüz grafiği bir orman olan bir yönlendirilmiş asiklik grafiktir.

Gelişmiş sınıflar

Daha gelişmiş grafik türleri şunlardır:

Grafiklerin özellikleri

Bir grafiğin iki kenarı, ortak bir köşeyi paylaşıyorlarsa bitişik olarak adlandırılır . Yönlendirilmiş bir grafiğin iki kenarı, birincinin başı ikincinin kuyruğuysa, ardışık olarak adlandırılır . Benzer şekilde, ortak bir kenarı paylaşıyorlarsa ( ilki kuyruk ve ikincisi bir kenarın başıysa ardışık) iki köşe bitişik olarak adlandırılır , bu durumda ortak kenarın iki köşeyi birleştirdiği söylenir . Bir kenar ve bu kenardaki bir tepe noktasına olay denir .

Sadece bir köşesi olan ve hiçbir kenarı olmayan grafa önemsiz graf denir . Yalnızca köşeleri olan ve kenarları olmayan bir graf , kenarsız graf olarak bilinir . Köşeleri ve kenarları olmayan grafiğe bazen boş grafik veya boş grafik denir , ancak terminoloji tutarlı değildir ve tüm matematikçiler bu nesneye izin vermez.

Normalde, bir grafiğin köşeleri, bir kümenin öğeleri olarak yapıları gereği ayırt edilebilirdir. Bu tür bir graf köşe etiketli olarak adlandırılabilir . Bununla birlikte, birçok soru için köşeleri ayırt edilemez olarak ele almak daha iyidir. (Tabii ki, köşeler grafiğin özellikleriyle, örneğin, gelen kenarların sayısıyla hala ayırt edilebilir.) Aynı açıklamalar kenarlar için de geçerlidir, bu nedenle kenar etiketli grafiklere kenar etiketli denir . Kenarlara veya tepe noktalarına etiket yapıştırılmış grafikler daha genel olarak etiketli olarak adlandırılır . Sonuç olarak, köşeleri ayırt edilemez ve kenarları ayırt edilemez olan grafiklere etiketsiz denir . (Literatürde, etiketli terimi , yalnızca farklı köşeleri veya kenarları ayırt etmeye yarayan etiketlemenin yanı sıra, diğer etiketleme türleri için de geçerli olabilir.)

Kategori tüm grafiklerin olduğu virgül kategorisi Seti ↓ D D Seti → Seti geçerli: funktor kümesi alarak ler için s × s .

Örnekler

Altı köşesi ve yedi kenarı olan bir grafik.
  • Diyagram, grafiğin köşeleri ve kenarları olan şematik bir temsilidir.
  • Olarak bilgisayar biliminin , yönlendirilmiş grafikleri bilgi (örneğin, temsil etmek için kullanılır kavramsal grafiği ), sonlu hal makinesi ve bir çok başka ayrık yapılar.
  • Bir X kümesindeki ikili ilişki R , yönlendirilmiş bir grafiği tanımlar. Bir eleman X ve X bir eleman doğrudan bir öncülüdür y ve X ancak ve ancak xRy .
  • Yönlendirilmiş bir grafik, Twitter gibi bilgi ağlarını , bir kullanıcının diğerini takip ettiği şekilde modelleyebilir .
  • Yönlendirilmiş grafiklerin özellikle düzenli örnekleri, sonlu olarak oluşturulmuş grupların Cayley grafikleri ve ayrıca Schreier koset grafikleri tarafından verilir.
  • Gelen Kategori teorisi , her küçük kategorisi olan köşe kenarları kategorisinin oklar kategorisinin amaçları ve olduğu bir temel yönlendirilmiş ufak matbaa sahiptir. Kategori teorisi dilinde, biri olduğunu söylüyor unutkan funktor gelen küçük kategorilerin kategorisine için sadaklar kategorisinde .

Grafik işlemleri

Aşağıdaki kategorilerde sınıflandırılabilecek ilk grafiklerden yeni grafikler üreten birkaç işlem vardır:

genellemeler

Bir hipergrafta , bir kenar ikiden fazla köşeyi birleştirebilir.

Bir yönsüz grafiği olarak görülebilir simpleksel kompleksi 1- oluşan simplices (kenarları) ve 0-simplices (vertices). Bu nedenle, kompleksler, daha yüksek boyutlu basitlere izin verdikleri için grafiklerin genellemeleridir.

Her grafik bir matroide yol açar .

Gelen bir model teori , bir grafiktir bir olan bir yapı . Ancak bu durumda, kenar sayısında bir sınırlama yoktur: herhangi bir ana sayı olabilir , bkz. sürekli grafik .

Olarak işlemsel biyoloji , güç grafiği analizi yönsüz grafikler alternatif bir temsili olarak güç grafikler getirmektedir.

Olarak coğrafi bilgi sistemleri , geometrik ağlar yakın grafikler örnek alınarak edilir ve pek çok fikir almaya grafik teorisi yol ağları veya yerel şebekeden mekansal analizi gerçekleştirmek için.

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

Dış bağlantılar