Çizgi grafiği

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. Ç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 ile kenar grafiği, değişim grafiği, ek grafik ve türetilmiş grafik vardır.

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ı. Ç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.

Resmi tanımlama

Bir G grafiği verildiğinde, çizgi grafiği L ( G ) şöyle bir grafiktir:

• Her bir köşe L (G) G, bir kenarı temsil eder; ve
• L ( G ) ' nin iki köşesi, ancak ve ancak karşılık gelen kenarları G'de ortak bir uç noktayı paylaşıyorsa ("olaydır") bitişiktir .

Yani, G'nin kenarlarının kesişim grafiğidir ve her bir kenarı, iki uç noktası kümesi ile temsil eder.

Örnek

Aşağıdaki şekiller bir grafiği (solda, mavi köşeli) ve çizgi grafiğini (sağda, yeşil köşeli) gösterir. Çizgi grafiğin her tepe noktası, orijinal grafikte karşılık gelen kenarın uç nokta çifti ile etiketlenmiş olarak gösterilir. Örneğin, sağdaki 1,3 etiketli yeşil köşe, 1 ve 3 numaralı mavi köşeler arasındaki soldaki kenara karşılık gelir. Yeşil köşe 1,3, diğer üç yeşil köşeye bitişiktir: 1,4 ve 1,2 (mavi grafikte uç noktası 1'i paylaşan kenarlara karşılık gelir) ve 4,3 (mavi grafikte uç nokta 3'ü paylaşan bir kenara karşılık gelir) ).

• 
  Grafik G
• 
  G'deki kenarlardan oluşturulan L (G) cinsinden tepe noktaları
• 
  L (G) 'de eklenen kenarlar
• 
  Çizgi grafiği L (G)

Özellikleri

Temel grafiğin çevrilmiş özellikleri

Sadece kenarlar arasındaki bitişikliğe bağlı olan bir G grafiğinin özellikleri, köşeler arasındaki bitişikliğe bağlı olan L ( G ) 'de eşdeğer özelliklere çevrilebilir. Örneğin, G'deki bir eşleştirme, ikisi bitişik olmayan ve L ( G ) 'de ikisi bitişik olmayan, yani bağımsız bir küme olan bir köşe kümesine karşılık gelen bir kenar kümesidir.

Böylece,

• Bağlı bir grafiğin çizgi grafiği bağlıdır. G, bağlı ise, bir içeren bir yol L köşe (G) herhangi iki içeren L (G) 'de bir yol anlamına kenarlarından herhangi iki bağlantı. Bununla birlikte, bazı izole köşeleri olan ve bu nedenle bağlantısı kesilen bir G grafiği yine de bağlantılı bir çizgi grafiğine sahip olabilir.
• Bir çizgi grafiğin bir artikülasyon noktası vardır, ancak ve ancak temeldeki grafik hiçbir uç noktanın birinci derecesine sahip olmadığı bir köprüye sahipse.
• N köşenin ve m, kenarlı bir grafik G, satır grafik L köşelerin (G) sayısı m ve L (G) kenarlarının sayısı karelerinin yarısı toplamıdır derece köşe bölgesindeki G, eksi m .
• Bir bağımsız ayar L (G) bir karşılık gelen eşleştirme G. Özel olarak, bir maksimum bağımsız ayar L (G) 'ye karşılık gelir , maksimum karşılaştırma G. Maksimum eşleşmeler polinom zamanda bulunabildiğinden, daha genel grafik aileleri için maksimum bağımsız küme probleminin sertliğine rağmen, maksimum bağımsız çizgi grafik setleri de olabilir. Benzer şekilde, bir gökkuşağı bağımsız ayar L (G) bir karşılık gelen gökkuşağı eşleme G.
• Bir G grafiğinin kenar kromatik numarası, çizgi grafiğinin L ( G ) köşe kromatik sayısına eşittir.
• Kenar geçişli grafiğin çizgi grafiği köşe geçişlidir . Bu özellik, ( Petersen grafiği gibi) tepe geçişli ancak Cayley grafikleri olmayan grafik aileleri oluşturmak için kullanılabilir: G, en az beş köşesi olan, iki uçlu olmayan ve tek bir tepe noktasına sahip bir kenar geçişli grafikse derece, o zaman L ( G ) bir tepe geçişli Cayley olmayan grafiktir.
• Bir G grafiğinin bir Euler döngüsü varsa, yani, G bağlıysa ve her tepe noktasında çift sayıda kenara sahipse, G'nin çizgi grafiği Hamiltoniyen'dir . Ancak, çizgi grafiklerindeki tüm Hamilton döngüleri bu şekilde Euler döngülerinden gelmez; örneğin, bir Hamilton grafiği G'nin çizgi grafiğinin kendisi, G'nin Eulerian olup olmadığına bakılmaksızın Hamiltoniyendir.
• İki basit grafik izomorfikse, çizgi grafikleri de izomorftur. Whitney grafiği izomorfizm teoremi, bir çift grafiğin tümü için bunun tersini sağlar.
• Karmaşık ağ teorisi bağlamında, rastgele bir ağın çizgi grafiği, küçük dünya özelliği (tüm köşe çiftleri arasındaki kısa yolların varlığı) ve derece dağılımının şekli gibi ağın birçok özelliğini korur. Evans & Lambiotte (2009), karmaşık bir ağda köşe kümelerini bulmaya yönelik herhangi bir yöntemin çizgi grafiğe uygulanabileceğini ve bunun yerine kenarlarını kümelemek için kullanılabileceğini gözlemler.

Dış bağlantılar

• Line graphs 8 Ağustos 2020 tarihinde Wayback Machine sitesinde arşivlendi., Information System on Graph Class Inclusions 7 Şubat 2021 tarihinde Wayback Machine sitesinde arşivlendi.
• Eric W. Weisstein, Line Graph (MathWorld)