Çizge kuramı, nesneler ve bu nesneler arasındaki ilişkileri modellemek için kullanılan güçlü bir matematiksel araçtır. Günlük yaşamda karşılaştığımız birçok karmaşık sistem, çizgeler yardımıyla basitleştirilerek analiz edilebilir. Örneğin, bir futbol ligindeki takımlar ve bu takımların birbirleriyle yaptıkları maçlar, ya da bir davete katılan kişiler ve bu kişilerin birbirleriyle tokalaşma durumları birer çizge modeli oluşturur.
Matematiksel olarak bir çizge, köşe noktaları (veya düğümler) kümesi ile bu noktaları birbirine bağlayan kenarlar (veya çizgiler) kümesinden oluşur. Çizgeler görselleştirilirken köşe noktaları harflerle (a, b, c...) veya isimlerle temsil edilirken, aralarındaki ilişkiler bu noktaları birleştiren düz veya eğri çizgilerle gösterilir. İki köşe noktası arasında bir kenar bulunması, bu iki noktanın birbiriyle doğrudan ilişkili olduğunu gösterir.
Çizgelerin analizi yapılırken en temel kavramlardan biri komşuluk ilişkisidir. Bir çizgede u ve v gibi iki köşe noktası arasında doğrudan bir kenar mevcutsa, bu noktalara komşu noktalar denir. Komşuluk ilişkisi, sistemdeki doğrudan etkileşimleri ve erişilebilirliği gösteren en temel yapı taşıdır.
Bir çizgedeki her bir köşe noktasının sistem içindeki önemini ve bağlantı yoğunluğunu ölçmek için derece kavramı kullanılır. Bir köşe noktasından çıkan veya bu noktaya bağlanan kenar sayısına o köşe noktasının derecesi denir. Bir u köşe noktasının derecesi d(u) sembolü ile gösterilir. Örneğin, bir tokalaşma çizgesinde herkesle tokalaşan bir kişinin temsil edildiği köşe noktasının derecesi en yüksek olacaktır.
Çizge kuramının en temel ve klasik sonuçlarından biri El Sıkışma Teoremi (Handshaking Theorem) olarak bilinir. Bu teoreme göre, bir çizgedeki tüm köşe noktalarının derecelerinin toplamı, çizgedeki toplam kenar sayısının tam olarak iki katına eşittir. Bunun nedeni, her bir kenarın iki uca sahip olması ve dereceler toplanırken her kenarın her iki uç noktası için de birer kez olmak üzere toplamda iki kez sayılmasıdır.
El Sıkışma Teoremi'nin doğrudan bir sonucu olarak, bir çizgedeki tüm köşe noktalarının derecelerinin toplamı her zaman çift bir sayı olmak zorundadır. Buradan hareketle, herhangi bir çizgede derecesi tek sayı olan köşe noktalarının sayısı da her zaman çift olmak zorundadır. Derecesi tek olan noktaların sayısı tek olsaydı, toplam derece tek sayı olurdu ki bu durum teoremle çelişir.
Çizge kuramının doğuşu, 18. yüzyılda ünlü matematikçi Leonhard Euler'in Königsberg şehrindeki yedi köprü problemini çözmesiyle gerçekleşmiştir. Pregel nehriyle ayrılan dört bölgeyi birbirine bağlayan yedi köprünün her birinden tam olarak bir kez geçerek tüm şehri dolaşmanın mümkün olup olmadığı sorusu, Euler tarafından bir çizge problemine dönüştürülmüştür. Euler, kara parçalarını köşe noktaları, köprüleri ise kenarlar olarak modellemiştir.
Euler, bir çizgede her kenardan tam olarak bir kez geçen bir gezintinin (Euler gezintisi) var olabilmesi için köşe noktalarının derecelerini incelemiştir. Eğer bir gezinti başladığı noktadan farklı bir noktada bitiyorsa, başlangıç ve bitiş noktalarının dereceleri tek sayı, diğer tüm ara noktaların dereceleri ise çift sayı olmalıdır. Eğer gezinti başladığı noktada bitiyorsa (Euler turu), tüm köşe noktalarının dereceleri çift sayı olmak zorundadır.
Königsberg köprüleri modelinde tüm bölgelerin (köşe noktalarının) dereceleri tek sayı (5, 3, 3, 3) olduğundan ve derecesi tek olan nokta sayısı ikiden fazla (dört adet) olduğundan, her köprüden tam olarak bir kez geçerek yapılacak bir gezintinin imkansız olduğu matematiksel olarak kanıtlanmıştır. Bu analiz, topoloji ve çizge kuramının ilk resmi uygulaması kabul edilir.
Bir çizgenin kenarları düzlemde birbirleriyle kesişmeyecek şekilde çizilebiliyorsa, bu çizgeye düzlemsel çizge denir. Düzlemsel çizgeler, özellikle elektronik devre kartı tasarımlarında yolların birbirinin üzerinden atlamadan çizilmesi gereken durumlarda hayati öneme sahiptir. K4 tam çizgesi düzlemsel bir çizgeyken, K5 tam çizgesi düzlemsel değildir.
Düzlemsel ve tek parçalı çizgeler için geçerli olan Euler Formülü, çizgenin bölge sayısı (b), köşe noktası sayısı (k) ve kenar (ayrıt) sayısı (a) arasındaki ilişkiyi kurar. Formüle göre: b + k = a + 2 eşitliği her zaman geçerlidir. Buradaki bölge sayısı, çizgenin düzlemi ayırdığı kapalı alanlar ile en dıştaki sonsuz genişlikteki açık bölgenin toplamını ifade eder.
Euler formülü aynı zamanda prizma, piramit ve küp gibi tüm konveks çokyüzlü cisimler için de geçerlidir. Bu cisimlerin yüz sayısı (bölge sayısı), köşe sayısı ve ayrıt sayısı arasındaki ilişki yine aynı formülle hesaplanır. Örneğin, klasik bir futbol topu düzgün 20 yüzlünün köşelerinin kesilmesiyle elde edilen 32 yüzlü (12 beşgen, 20 altıgen) bir konveks çokyüzlüdür ve bu formülü doğrular.
Çizge boyama, komşu olan köşe noktalarının farklı renklere boyanması şartıyla bir çizgenin tüm köşelerini boyamak için gereken en az renk sayısını bulma problemidir. Bu problem, uyumsuz nesnelerin (örneğin birbiriyle geçinemeyen balık türlerinin veya aynı saatte yapılması gereken sınavların) birbirinden ayrılması gereken optimizasyon problemlerinde sıklıkla kullanılır.
Tarihsel olarak çizge boyama, harita boyama problemiyle başlamıştır. Siyasi haritalarda ortak sınırı olan ülkelerin farklı renklerde gösterilmesi istenir. Francis Guthrie tarafından 1850'lerde ortaya atılan ve uzun süre çözülemeyen 'Dört Renk Problemi', her düzlemsel haritanın (ve dolayısıyla her düzlemsel çizgenin) komşu bölgeler farklı renkte olacak şekilde en fazla dört renk kullanılarak boyanabileceğini savunur. Bu iddia 1976'da bilgisayar yardımıyla kanıtlanmıştır.
Çizge boyama ile ilgili bir diğer önemli teorem Brook Teoremi'dir (1941). Bu teoreme göre, bir çizgenin tüm köşe noktalarının derecesi en fazla d ise, bu çizgenin köşe noktaları komşu noktalar farklı renklerde olacak şekilde en fazla d + 1 renk kullanılarak boyanabilir. Bu teorem, boyama işlemlerinde üst sınır belirlemek için kullanılır.
Çizge kuramında döngü içermeyen tek parçalı (bağlantılı) çizgelere ağaç denir. Ağaçlar, en az maliyetle bağlantı kurma problemlerinde, soy ağaçlarında ve bilgisayar dosya dizini yapılarında yaygın olarak kullanılır. Bir ağaçta, herhangi iki köşe noktası arasında sadece tek bir yol bulunur ve kenarlardan biri çıkarılırsa çizgenin tek parça olma özelliği kaybolur.
Arthur Cayley, n tane köşe noktası olan birbirinden farklı ağaçların sayısının n^(n-2) olduğunu kanıtlamıştır. Köşe sayısı arttıkça olası ağaç sayısı çok hızlı bir şekilde büyür. Bu nedenle, belirli maliyetlere sahip kenarlardan oluşan bir çizgede, tüm köşeleri birbirine bağlayan en düşük maliyetli ağacı (optimal ağaç) bulmak için sistematik yöntemlere ihtiyaç duyulur.
Kruskal Algoritması, optimal ağacı bulmak için kullanılan en popüler yöntemlerden biridir. Bu algoritma, çizgedeki kenarları en düşük maliyetliden en yüksek maliyetliye doğru sıralar. Her adımda en ucuz kenar seçilir ve eğer bu kenarın eklenmesi çizgede bir döngü (kapalı devre) oluşturmuyorsa ağaca dahil edilir. Tüm köşeler birbirine bağlanana kadar bu işleme devam edilir.