Graf (matematik)

Vikipedi, özgür ansiklopedi
Gezinti kısmına atla Arama kısmına atla
Altı köşeli ve yedi kenarlı bir graf.

Matematikte ve daha spesifik olarak graf (çizge) teorisinde, graf, nesne çiftlerinin bir anlamda "ilişkili" olduğu bir dizi nesne kümesini belirleyen bir yapıdır. 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 düğüm çiftlerinin her birine bir kenar, ayrıt ( bağlantı veya çizgi olarak da adlandırılır) adı verilir. [1] Tipik olarak, bir graf, kenarları için çizgiler veya eğriler ile birleştirilen, düğümler için bir nokta veya daire kümesi olarak diyagram şeklinde gösterilir. Graflar ayrık matematikte çalışmanın amaçlarından biridir.

Kenarlar yönlendirilmiş veya yönlendirilmemiş olabilir. Örneğin, düğümler bir partideki insanları temsil ediyorsa ve iki kişi arasında el sıkışırlarsa bir kenar varsa, o zaman bu grafik yönlendirilmez, çünkü herhangi bir A kişisi B kişiyle ancak B ile A el sıkışırsa el sıkışabilir. Aksine, eğer bir A kişisinden bir B kişisine herhangi bir kenarı A hayranlığı B'ye karşılık gelirse, o zaman bu graf yönlendirilir, çünkü hayranlık zorunludur. İlk graf türüne yönlendirilmemiş graf, sonraki graf türüne yönlendirilmiş graf denir.

Çizgeler, graf teorisi tarafından incelenen temel konudur. "Graf" kelimesi ilk olarak bu anlamda 1878'de James Joseph Sylvester tarafından kullanılmıştır. [2] [3]

Tanımlar[değiştir | kaynağı değiştir]

Çizge teorisindeki tanımlar değişkendir. Aşağıdakiler, grafları ve ilgili matematiksel yapıları tanımlamanın daha temel yollarından bazılarıdır.

Graf[değiştir | kaynağı değiştir]

Üç köşeli ve üç kenarlı bir graf.

Graf (Bazen ayırt etmeye yönelik sınıflandırırken, yönsüz graf ve yönlü graf, veya basit graf , katlı graf olarak adlandırılırlar) [4] [5] bir çift elemandan oluşur G = (V, E), V elemanına köşe denir ve E elemanı kenarlar (bazen bağlantılar veya çizgiler ) olarak adlandırılan iki kümeden (iki ayrı öğeye sahip - iki kenar ve bağlayan çizgi- kümeler) oluşan bir dizidir. Her kenar iki ucunda düğüm olacak şekilde tanımlanır.

Bir kenarın {x, y}, düğümleri olan x ve y kenaralrın uç noktalarıdır. Kenar x ve y'yi ileşkilendirir ve x ve y'yi birbirine bağlar. Bir düğüm herhangi bir kenara ait olmayabilir.

Bir katlı graf, aynı köşe çiftine bitişik çoklu kenarlara izin veren bir genellemedir. Bazı metinlerde katlı graflara basitçe graflar da denir. [4] [6]

Yönlü graf[değiştir | kaynağı değiştir]

Üç köşeli ve dört yönlendirilmiş kenarlı yönlü bir graf (çift ok her yöndeki bir kenarı temsil eder).

Yönlü graf veya digraf, kenarların oryantasyonlu-yönlendirilmiş olduğu bir graftır.

Karışık graf[değiştir | kaynağı değiştir]

Ağırlıklı graf[değiştir | kaynağı değiştir]

On köşeli ve on iki kenarlı ağırlıklı bir grafik.

Graf çeşitleri[değiştir | kaynağı değiştir]

Yönlendirilmiş graf[değiştir | kaynağı değiştir]

Düzenli graf[değiştir | kaynağı değiştir]

Tam graf[değiştir | kaynağı değiştir]

Sonlu graf[değiştir | kaynağı değiştir]

Bağlı graf[değiştir | kaynağı değiştir]

Bipartit graf[değiştir | kaynağı değiştir]

Yol graf[değiştir | kaynağı değiştir]

Düzlemsel graf[değiştir | kaynağı değiştir]

Çember graf[değiştir | kaynağı değiştir]

Ağaç[değiştir | kaynağı değiştir]

Polytree[değiştir | kaynağı değiştir]

Gelişmiş sınıflar[değiştir | kaynağı değiştir]

Grafların özellikleri[değiştir | kaynağı değiştir]

Örnekler[değiştir | kaynağı değiştir]

Graf işlemleri[değiştir | kaynağı değiştir]

Genelleştirmeler[değiştir | kaynağı değiştir]

Ayrıca bakınız[değiştir | kaynağı değiştir]

  • Kavramsal graf
  • Graf (soyut veri türü)
  • Graf veritabanı
  • Graf çizimi
  • Graf teorisi konularının listesi
  • Graf teorisi yayınlarının listesi
  • Ağ teorisi

Notlar[değiştir | kaynağı değiştir]

  1. ^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. s. 19. ISBN 978-0-486-67870-2. Erişim tarihi: 8 Ağustos 2012. A graph is an object consisting of two sets called its vertex set and its edge set. 
  2. ^ Bakınız:
  3. ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. s. 35. ISBN 978-1-58488-090-5. 
  4. ^ a b Bender & Williamson 2010.
  5. ^ Bknz: Iyanaga and Kawada, 69 J, s. 234 veya Biggs, s. 4.
  6. ^ Graham et al., p. 5.

Kaynakça[değiştir | kaynağı değiştir]

Daha fazla okuma[değiştir | kaynağı değiştir]

Dış bağlantılar[değiştir | kaynağı değiştir]