Graf (matematik)

Matematikte graf ya da çizge, 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. 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önlü veya yönsüz 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şisiyle 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önsüz çizge, sonraki graf türüne yönlü çizge 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.Bakınız:

 J. J. Sylvester (7 Şubat 1878) "Chemistry and algebra,"  Nature, 17 : 284. . 284. sayfadan itibaren: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
 J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices,"  American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. . . "graf" terimi ilk kez bu yayımda sayfa 65'te geçer.

 Tanımlar 
Ç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 
küçükresim|Üç 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) Bknz:  Iyanaga and Kawada, 69 J, s. 234 veya Biggs, s. 4. bir çift elemandan oluşur ,  elemanına köşe denir ve  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 }, düğümleri olan  ve  kenarların uç noktalarıdır. Kenar  ve 'yi ileşkilendirir ve  ve 'yi birbirine bağlar. Bir düğüm herhangi bir kenara ait olmayabilir.

Bir katlı graf, aynı köşe çiftine bitişik birden fazla kenara izin veren bir genellemedir. Bazı metinlerde katlı graflara basitçe graflar da denir. Graham et al., p. 5. 

 Yönlü çizge 
Bir grafın kenarlarının yön belirtmesi durumunda bu grafa yönlü çizge ya da yönlü graf denir. Yönlü graflarda iki köşe arasında geçiş sadece tek yönde ve tek köşeden olur. 
küçükresim|Üç 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 

 Ağırlıklı graf 
küçükresim|On köşeli ve on iki kenarlı ağırlıklı bir grafik.

 Graf çeşitleri 

 Yönlendirilmiş graf 

 Düzenli graf 

 Tam graf 
Her köşeden herhangi diğer bir köşeye tek kenar üzerinden geçiş yapılabilen graflara tam graf denir. Yani tam graflarda tüm köşe ikilileri bağlıdır.

 Sonlu graf 

 Bağlı graf 

 İki parçalı graf 

 Yol graf 

 Düzlemsel graf 

 Çember graf 

 Ağaç 
İçerisinde döngü bulundurmayan graflara ağaç denir.

 Çoklu ağaç 

 Gelişmiş sınıflar 

 Grafların özellikleri 

 Örnekler 

 Graf işlemleri 

 Genellemeler 

 Ayrıca bakınız 

 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 

 Kaynakça 















 Konuyla ilgili yayınlar 


 Dış bağlantılar 


Kategori:Çizge teorisi