Multigraf - Multigraph

Birden çok kenarı (kırmızı) ve birkaç ilmiği (mavi) olan bir çoklu grafik. Tüm yazarlar çoklu grafiğin döngülere sahip olmasına izin vermez.

İçinde matematik ve daha spesifik olarak grafik teorisi, bir çoklu grafik bir grafik sahip olmasına izin verilen çoklu kenarlar (olarak da adlandırılır paralel kenarlar^[1]), yani, kenarlar aynısı var uç düğümler. Böylelikle iki köşe birden fazla kenar ile birleştirilebilir.

Birden çok kenarın iki farklı kavramı vardır:

• Kendi kimliği olmayan kenarlar: Bir kenarın kimliği, yalnızca bağlandığı iki düğüm tarafından tanımlanır. Bu durumda, "çoklu kenarlar" terimi, aynı kenarın bu iki düğüm arasında birkaç kez meydana gelebileceği anlamına gelir.
• Kendi kimliğine sahip kenarlar: Kenarlar, düğümler gibi ilkel varlıklardır. Birden çok kenar iki düğümü bağladığında, bunlar farklı kenarlardır.

Bir multigraf, bir hiper grafik Bu, bir kenarın yalnızca iki değil, herhangi bir sayıda düğümü bağlayabildiği bir grafiktir.

Bazı yazarlar için şartlar sahte yazı ve çoklu grafik eşanlamlıdır. Diğerleri için bir sahte yazı sahip olmasına izin verilen bir çoklu grafiğidir döngüler.

Yönlendirilmemiş multigrafi (kendi kimliği olmayan kenarlar)

Bir multigraf G bir sıralı çift G := (V, E) ile

• V a Ayarlamak nın-nin köşeler veya düğümler,
• E a çoklu set sıralanmamış köşe çiftlerinin adı verilen kenarlar veya çizgiler.

Yönlendirilmemiş multigrafi (kendi kimliğine sahip kenarlar)

Bir multigraf G sıralı üçlü G := (V, E, r) ile

• V a Ayarlamak nın-nin köşeler veya düğümler,
• E a Ayarlamak nın-nin kenarlar veya çizgiler,
• r : E → {{x,y} : x, y ∈ V}, her kenara sırasız bir uç nokta düğümü çifti atar.

Bazı yazarlar çoklu grafiğin sahip olmasına izin verir döngüler yani bir tepe noktasını kendisine bağlayan bir kenar,^[2] diğerleri bunları çağırırken sahte resimler, multigraph terimini döngü içermeyen durum için ayırarak.^[3]

Yönlendirilmiş multigrafi (kendi kimliği olmayan kenarlar)

Bir multidigraf bir Yönlendirilmiş grafik sahip olmasına izin verilen çoklu yaylar, yani, aynı kaynak ve hedef düğümlere sahip yaylar. Bir multidigraf G sıralı bir çift G := (V, Bir) ile

• V bir dizi köşeler veya düğümler,
• Bir çok sayıda sıralı köşe çiftleri adı verilen yönlendirilmiş kenarlar, yaylar veya oklar.

Bir karışık multigraf G := (V, E, Bir) ile aynı şekilde tanımlanabilir karışık grafik.

Yönlendirilmiş multigrafi (kendi kimliğine sahip kenarlar)

Bir multidigraf veya titreme G sıralı 4 parça G := (V, Bir, s, t) ile

• V a Ayarlamak nın-nin köşeler veya düğümler,
• Bir a Ayarlamak nın-nin kenarlar veya çizgiler,
• ${ displaystyle s: A rightarrow V}$, her bir kenara kaynak düğümünü atayarak,
• ${ displaystyle t: A rightarrow V}$, her bir kenara kendi hedef düğümünü atayarak.

Bu fikir, bir havayolunun sunduğu olası uçuş bağlantılarını modellemek için kullanılabilir. Bu durumda çoklu grafik bir Yönlendirilmiş grafik her ikisinin de uçmanın mümkün olduğunu göstermek için şehirleri birbirine bağlayan yönlendirilmiş paralel kenar çiftleri ile -e ve itibaren bu yerler.

İçinde kategori teorisi küçük kategori birleştirici bir kompozisyon yasası ve kompozisyon için sol ve sağ özdeşlik görevi gören her köşede ayırt edici bir öz döngü ile donatılmış bir multidigraf (kendi kimliğine sahip kenarları olan) olarak tanımlanabilir. Bu nedenle kategori teorisinde terim grafik standart olarak "multidigrafi" anlamına gelir ve bir kategorinin temelindeki multidigrafi, onun temeldeki digraph.

Etiketleme

Multigraphs ve multidigraphs da şu kavramını destekler: grafik etiketleme, benzer bir yolla. Ancak bu durumda terminolojide bir birlik yoktur.

Tanımları etiketli multigraflar ve etiketli multidigraflar benzerdir ve burada sadece sonuncularını tanımlarız.

Tanım 1: Etiketli bir multidigraf, bir etiketli grafik ile etiketli yaylar.

Resmi olarak: Etiketli bir multidigraf G, etiketli köşeler ve yaylar. Resmen bu bir 8-tuple ${ displaystyle G = ( Sigma _ {V}, Sigma _ {A}, V, A, s, t, ell _ {V}, ell _ {A})}$ nerede

• V bir köşe kümesidir ve A bir yay kümesidir.
• ${ displaystyle Sigma _ {V}}$ ve ${ displaystyle Sigma _ {A}}$ mevcut köşe ve yay etiketlerinin sonlu alfabeleridir,
• ${ displaystyle s iki nokta üst üste A sağ V}$ ve ${ displaystyle t iki nokta üst üste A sağ V}$ gösteren iki haritadır kaynak ve hedef bir yayın tepe noktası,
• ${ displaystyle ell _ {V} iki nokta üst üste V sağ yön Sigma _ {V}}$ ve ${ displaystyle ell _ {A} iki nokta üst üste A sağ yön Sigma _ {A}}$ köşelerin ve yayların etiketlemesini açıklayan iki haritadır.

Tanım 2: Etiketli bir multidigraf, bir etiketli grafik birden çok etiketli yaylar, yani aynı uç köşelerine ve aynı yay etiketine sahip yaylar (bu etiketli grafik kavramının makale tarafından verilen kavramdan farklı olduğunu unutmayın. grafik etiketleme ).

Ayrıca bakınız

• Çok boyutlu ağ
• Grafik teorisi terimleri sözlüğü
• Grafik teorisi

Notlar

Referanslar

• Balakrishnan, V. K. (1997). Grafik teorisi. McGraw-Hill. ISBN  0-07-005489-4.
• Bollobás, Béla (2002). Modern Grafik Teorisi. Matematikte Lisansüstü Metinler. 184. Springer. ISBN  0-387-98488-7.
• Chartrand, Gary; Zhang, Ping (2012). Grafik Teorisinde İlk Kurs. Dover. ISBN  978-0-486-48368-9.
• Diestel Reinhard (2010). Grafik teorisi. Matematikte Lisansüstü Metinler. 173 (4. baskı). Springer. ISBN  978-3-642-14278-9.
• Gross, Jonathan L .; Yellen, Jay (1998). Çizge Teorisi ve Uygulamaları. CRC Basın. ISBN  0-8493-3982-0.
• Gross, Jonathan L .; Yellen, Jay, editörler. (2003). Çizge Teorisi El Kitabı. CRC. ISBN  1-58488-090-2.
• Harary, Frank (1995). Grafik teorisi. Addison Wesley. ISBN  0-201-41033-8.
• Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel Boris (1993). "Dev bileşenin doğuşu". Rastgele Yapılar ve Algoritmalar. 4 (3): 231–358. arXiv:math / 9310236. Bibcode:1993math ..... 10236J. doi:10.1002 / rsa.3240040303. ISSN  1042-9832. BAY  1220220.
• Wilson, Robert A. (2002). Grafikler, Renklendirmeler ve Dört-Renk Teoremi. Oxford Science Publ. ISBN  0-19-851062-4.
• Zwillinger Daniel (2002). CRC Standart Matematik Tabloları ve Formülleri (31. baskı). Chapman & Hall / CRC. ISBN  1-58488-291-3.

Dış bağlantılar

• Bu makale içerir kamu malı materyal -denNIST belge:Siyah, Paul E. "Multigraf". Algoritmalar ve Veri Yapıları Sözlüğü.