Grafik Teorisi (graph theory)

Matematikte grafik teorisi, objeler arasındaki ikili ilişkileri modellemek için kullanılan matematiksel yapılar olan grafiklerin incelenmesidir. Bu kapsamda bir grafik, kenarlarla (bağlantılar veya çizgiler olarak da adlandırılır) birbirine bağlanan köşelerden (düğümler veya noktalar da denir) oluşur. Kenarların iki köşeyi simetrik olarak bağladığı yönsüz grafikler ile, kenarların iki köşeyi asimetrik olarak bağladığı yönlendirilmiş grafikler arasında bir ayrım yapılır. Grafikler ayrık matematikte çalışmanın temel objelerinden biridir.

Tanımlar

Grafik teorisinde tanımlar farklılık gösterir. Aşağıda grafikleri ve ilgili matematiksel yapıları tanımlamanın daha temel yollarından bazıları yer almaktadır.

·        Grafik: Terimin kısıtlı ama çok yaygın bir anlamıyla, bir grafik, aşağıdakileri içeren sıralı bir G = (V, E) çiftidir:

o   V, bir dizi köşe (düğümler veya noktalar olarak da adlandırılır),

o   E Í {{x. y} | x,y Î V ve x ¹ y}, sırasız köşe çiftleri olan (yani bir kenar iki farklı köşeyle ilişkilidir) bir kenarlar kümesidir (bağlantılar veya çizgiler olarak da adlandırılır).

·        Yönlendirilmiş grafik: Yönlendirilmiş bir grafik veya digraf, kenarların yönelimlere sahip olduğu bir grafiktir. Terimin sınırlı ama çok yaygın bir anlamında, yönlendirilmiş bir grafik, aşağıdakileri içeren sıralı bir G = (V, E) çiftidir:

o   V, bir dizi köşe (düğümler veya noktalar olarak da bilinir),

o   E Í {{x. y} | x,y Î V2 ve x ¹ y}, sıralı köşe çiftleri olan (yani bir kenar iki farklı köşeyle ilişkilendirilmiş) bir kenarlar kümesi (aynı zamanda yönlendirilmiş kenarlar, yönlendirilmiş bağlantılar, yönlendirilmiş çizgiler, oklar veya yaylar da denir).


(a) Bir grafiğin çizimi, (b) üç köşesi ve üç kenarı olan bir grafik, (c) üç köşesi ve dört yönlü kenarı olan yönlü bir grafik (çift ok, her yöndeki bir kenarı temsil eder).

 

https://en.wikipedia.org/wiki/Graph_theory

29 Aralık 2023

 

GERİ (matematik anasayfa)