Çizgi grafiği
From Wikipedia, the free encyclopedia
Grafik teorisinin matematiksel disiplininde, yönlendirilmemiş bir G grafiğinin çizgi grafiği, G'nin kenarları arasındaki bitişiklikleri temsil eden başka bir L (G) grafiğidir.. L(G) şu şekilde oluşturulur: G'deki her kenar için, L(G)'de bir tepe noktası yapılır; G'de ortak bir tepe noktasına sahip her iki kenar için, L(G)'de karşılık gelen köşeleri arasında bir kenar yapılır.
Hem Whitney (1932) hem de Krausz (1943) yapıyı bundan önce kullanmış olmasına rağmen, isim çizgisi grafiği Harary & Norman (1960) tarafından yazılan bir makaleden alınmıştır.[1] Çizgi grafiği için kullanılan diğer terimler arasında kaplama grafiği, türev, uçtan köşeye ikili, eşlenik, temsili grafik ve ϑ-obrazom [1] ile kenar grafiği, değişim grafiği, ek grafik ve türetilmiş grafik vardır.[2]
Hassler Whitney (1932), istisnai bir durumla, bağlantılı bir G grafiğinin yapısının, çizgi grafiğinden tamamen kurtarılabileceğini kanıtladı.[3] Çizgi grafiklerin diğer birçok özelliği, alttaki grafiğin özelliklerini köşelerden kenarlara çevirerek takip eder ve Whitney teoremine göre aynı çeviri diğer yönde de yapılabilir. Çizgi grafikler pençesizdir ve iki parçalı grafiklerin çizgi grafikleri mükemmeldir. Çizgi grafikler dokuz yasak alt grafik ile karakterize edilir ve doğrusal zamanda tanınabilir.
Çizgi grafikler, çoklu grafiklerin çizgi grafikleri, hiper grafiklerin çizgi grafikleri ve ağırlıklı grafiklerin çizgi grafikleri dahil olmak üzere bir çizgi grafiği kavramının çeşitli uzantıları incelenmiştir.