Çevrim alanı - Cycle space

Olarak grafik teorisi , matematik bir kolu (ikili) döngüsü yer bir bir yönsüz grafik olan bir dizi hatta derecelik Alt Graflar.

Bu alt grafik kümesi cebirsel olarak iki elemanlı sonlu alan üzerinde bir vektör uzayı olarak tanımlanabilir . Bu boşluğun boyutu , grafiğin devre sıralamasıdır . Aynı uzay , grafiğin ilk homoloji grubu olarak cebirsel topolojiden de tanımlanabilir . Homoloji teorisi kullanılarak, ikili çevrim uzayı, uzayları rastgele halkalar üzerinden çevirmek için genelleştirilebilir .

Tanımlar

Grafik teorisi

Bir kapsayan alt grafiğinin , belirli bir grafiktir ve G herhangi bir alt kümesi ile ilgili tanımlanabilir S kenarlarının G . Alt grafiğinin aynı seti vardır köşeler olarak G kendisi (bu kelime "kapsayan" anlamı), fakat elemanlarını sahip S kenarlarından olarak. Bu durumda, bir grafiktir G ile m kenarları 2 vardır ^m de dahil olmak üzere kapsayan subgraphs, G kendisinde hem de boş grafik olarak köşe aynı sette G . Bir grafik her kapsayan Alt Graflar toplanması G oluşturan kenar alanı içinde G .

Bir G grafiğinin veya alt grafiklerinden birinin, köşelerinin her birinin çift ​​sayıda olay kenarı varsa (bu sayıya tepe derecesi denir) Euler olduğu söylenir . Bu mülk adını 1736'da Königsberg'in Yedi Köprüsü'ndeki çalışmasında kanıtlayan Leonhard Euler'den almıştır , bağlantılı bir grafiğin her kenarı yalnızca ve ancak Eulerian ise tam olarak bir kez ziyaret eden bir turu olduğunu kanıtlamıştır . Ancak, bir Euler alt grafiğinin bağlanması gerekmez; örneğin, tüm köşelerin birbirinden kopuk olduğu boş grafik Eulerian'dır. Bir grafiğin döngü alanı, Eulerian yayılan alt grafiklerinin toplamıdır.

Cebir

Belirli bir grafiğin iki kapsayan alt grafiğine kümelerin birleşimi veya kesişimi gibi herhangi bir ayar işlemi uygulanırsa , sonuç yine bir alt grafik olacaktır. Bu şekilde, rastgele bir grafiğin kenar uzayı bir Boole cebri olarak yorumlanabilir .

İki Euler alt grafiğinin (kırmızı ve yeşil) simetrik farkı, Euler alt grafiğidir (mavi).

Döngü uzayının da cebirsel bir yapısı vardır, ancak daha kısıtlayıcıdır. İki Euler alt grafiğinin birleşimi veya kesişimi Eulerian olmayabilir. Bununla birlikte, iki Euler alt grafiğinin (verilen iki grafikten tam olarak birine ait olan kenarlardan oluşan grafik) simetrik farkı yine Euler'dir. Bu, çift sayıda öğeye sahip iki kümenin simetrik farkının da eşit olduğu gerçeğinden kaynaklanır. Bu gerçeği her bir tepe noktasının mahallelerine ayrı ayrı uygulamak , simetrik fark operatörünün Euler olma özelliğini koruduğunu gösterir.

Simetrik fark işlemi altında kapalı bir kümeler ailesi cebirsel olarak iki elemanlı sonlu alan üzerinde bir vektör uzayı olarak tanımlanabilir . Bu alanın 0 ve 1 olmak üzere iki öğesi vardır ve toplama ve çarpma işlemleri, modulo 2 olarak alınan tamsayıların bilinen toplama ve çarpma işlemleri olarak tanımlanabilir . Bir vektör uzayı, bilinen gerçek vektör uzaylarının özelliklerini genelleştiren belirli özellikleri karşılayan bir toplama ve skaler çarpma işlemi ile birlikte bir dizi öğeden oluşur ; döngü uzayı için, vektör uzayının elemanları Euler alt grafikleri, toplama işlemi simetrik farklılaşmadır, skaler 1 ile çarpma özdeşlik işlemidir ve skaler 0 ile çarpma her elemanı boş grafiğe götürür, bu da döngü alanı için ek kimlik öğesi. ${\ displaystyle \ mathbb {Z} _ {2}}$

Simetrik farkı toplama olarak kullanırsak kenar uzayı da bir vektör uzayıdır . Vektör uzayları olarak, grafiğin döngü uzayı ve kesim alanı (grafiğin kesimlerini kapsayan kenar kümeleri ailesi ) , kenar uzayında birbirlerinin ortogonal tamamlayıcılarıdır . Bir dizi bu araçlar bir grafik kenarları bir kesim meydana getirir, eğer her Euler subgraph ile ortak kenarları bir çift sayı sahip olması durumunda ve bir Euler alt grafiğini oluşturması ve her kesme ortak kenarları ile bir çift sayıda sahip olması durumunda . Bu iki boşluk ortogonal tamamlayıcılar olmasına rağmen, bazı grafiklerin her ikisine de ait olan boş olmayan alt grafikleri vardır. Böyle bir alt grafik (bir Euler kesimi), ancak ve ancak çift ​​sayıda uzanan ormana sahipse , grafiğin bir parçası olarak mevcuttur . ${\ displaystyle \ mathbb {Z} _ {2}}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle G}$${\ displaystyle G}$

Topoloji

Yönlendirilmemiş bir grafik , köşeleri sıfır boyutlu basitler ve kenarları tek boyutlu basitler olarak olan basit bir kompleks olarak görülebilir. Zinciri kompleksi bu topolojik alan kenarından alanı ve aşağıdakilerden oluşmaktadır tepe alanı tek-derece olan setine bir kapsayan alt grafiğini (kenar alanı bir elemanı) eşleştiren bir sınır operatör tarafından bağlanan (vertices setlerinin Boole cebri), köşeler (köşe boşluğunun bir öğesi). homoloji grubu

${\ displaystyle H_ {1} (G, \ mathbb {Z} _ {2})}$

köşe uzayının sıfır elemanıyla eşleşen kenar uzayının öğelerinden oluşur; bunlar tam olarak Euler alt grafikleri. Grup işlemi, Euler alt grafikleri üzerindeki simetrik fark işlemidir.

Bu yapıda rastgele bir halka ile değiştirilmesi , döngü uzaylarının tanımının, halka üzerinde modüller oluşturan, verilen halkadaki katsayılarla döngü alanlarına genişletilmesine izin verir . Özellikle, integral döngü uzayı boşluktur ${\ displaystyle \ mathbb {Z} _ {2}}$

${\ displaystyle H_ {1} (G, \ mathbb {Z}).}$

Grafiğin keyfi bir yönünü seçerek ve bir grafiğin bir integral döngüsünü , özelliğiyle (kenarlar üzerindeki serbest değişmeli grubun bir öğesi) kenarlarına bir tamsayı ataması olarak tanımlayarak, grafik teorik terimlerle tanımlanabilir. ki, her bir tepe noktasında, gelen kenarlara atanan sayıların toplamı, giden kenarlara atanan sayıların toplamına eşittir. ${\ displaystyle G}$${\ displaystyle G}$

Kenarlara atanan tüm sayıların sıfırdan farklı olduğu ek özelliğine sahip bir veya üyesine (döngü alanı modülo ), hiçbir yerde sıfır olmayan akış veya hiçbir yerde sıfır olmayan akış denir. ${\ displaystyle H_ {1} (G, \ mathbb {Z})}$${\ displaystyle H_ {1} (G, \ mathbb {Z} _ {k})}$${\ displaystyle k}$${\ displaystyle k}$

Devre sıralaması

Bir vektör alan olarak, bir grafiğin döngüsü alan boyutu köşe, kenarlar ve bağlı bileşenleri olan . Bu sayı, topolojik olarak grafiğin ilk Betti numarası olarak yorumlanabilir . Grafik teorisinde, grafiğin devre sıralaması , döngüsel sayısı veya sıfır olması olarak bilinir . ${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle c}$ ${\ displaystyle m-n + c}$

Rütbe için bu formülün, döngü uzayının iki elemanlı alan üzerinde bir vektör uzayı olması gerçeğiyle birleştirilmesi, döngü uzayındaki toplam eleman sayısının tam olduğunu gösterir . ${\ displaystyle 2 ^ {m-n + c}}$

Döngü tabanları

Bir vektör uzayının temeli , diğer tüm öğelerin temel öğelerin doğrusal bir kombinasyonu olarak yazılabileceği özelliğine sahip öğelerin minimum bir alt kümesidir. Sonlu boyutlu bir uzayın her temeli, uzayın boyutuna eşit olan aynı sayıda öğeye sahiptir. Döngü uzayı durumunda, temel, her Euler alt grafiğinin bir temel elemanlar ailesinin simetrik farkı olarak yazılabilmesi özelliğine sahip, tam olarak Euler alt grafiklerinin bir ailesidir. ${\ displaystyle m-n + c}$

Varoluş

Tarafından Veblen'in teoremi , belirli bir grafiğin her Euler subgraph ayrılacak olabilir basit döngü bütün çıkıntılar derecesi sıfır ya da iki ve burada derecesi iki köşe bağlı bir dizi oluşturan, milleri vardır subgraphs ki burada,. Bu nedenle, temel unsurların hepsinin basit döngüler olduğu bir temel bulmak her zaman mümkündür. Böyle bir temele, verilen grafiğin döngü temeli denir . Daha güçlü bir şekilde, temel elemanların indüklenmiş döngüleri veya hatta ( 3 köşe bağlantılı bir grafikte ) indüklenmiş döngülerin, çıkarılması kalan grafiği ayırmadığı bir temel bulmak her zaman mümkündür .

Temel ve zayıf temel temeller

Bir döngü temeli oluşturmanın bir yolu , grafiğin genişleyen bir ormanını oluşturmak ve ardından ormana ait olmayan her kenar için, ormandaki uç noktaları birbirine bağlayan yolla birlikte  oluşan bir döngü oluşturmaktır . Bu şekilde oluşturulan döngü seti doğrusal olarak bağımsızdır (her biri diğer döngülerin hiçbirine ait olmayan bir kenar içerir ) ve temel olmak için doğru boyuta sahiptir, bu nedenle zorunlu olarak bir temeldir. Bu şekilde oluşturulan temele, temel döngü temeli denir . ${\ displaystyle e}$${\ displaystyle C_ {e}}$${\ displaystyle e}$${\ displaystyle e}$${\ displaystyle C_ {e}}$${\ displaystyle e}$${\ displaystyle m-n + c}$

Döngü bazında döngülerin doğrusal sıralaması varsa, öyle ki her döngü bir önceki döngünün parçası olmayan en az bir kenar içerir, o zaman döngü temeli zayıf temel olarak adlandırılır . Her temel döngü temeli zayıf bir şekilde temeldir (tüm doğrusal sıralamalar için), ancak bunun tersi zorunlu değildir. Zayıf bir şekilde temel olmayan grafikler ve bu grafikler için döngü tabanları vardır.

Minimum ağırlık tabanları

Bir grafiğin kenarlarına gerçek sayı ağırlıkları verilirse, bir alt grafiğin ağırlığı, kenarlarının ağırlıklarının toplamı olarak hesaplanabilir. Döngü uzayının minimum ağırlık temeli zorunlu olarak bir döngü temelidir ve polinom zamanında inşa edilebilir. Minimum ağırlık temeli her zaman zayıf bir şekilde temel değildir ve bu olmadığında, mümkün olan minimum ağırlık ile zayıf temel temeli bulmak NP kadar zordur .

Düzlemsel grafikler

Homoloji

Düzlem içine bir düzlemsel grafik yerleştirilirse, bunun zincir kenarları ve köşeleri kompleksi, grafiğin yüz setlerini de içeren daha yüksek boyutlu bir zincir kompleksine gömülebilir. Bu zincir kompleksinin sınır haritası, herhangi bir 2 zinciri (bir dizi yüz), 2 zincirdeki tek sayıda yüze ait olan kenar kümesine götürür. 2 zincirin sınırı, zorunlu olarak bir Euler alt grafiğidir ve her Euler alt grafiği, bu şekilde tam olarak iki farklı 2-zincirden (her biri diğerinin tamamlayıcısıdır ) üretilebilir . Bundan, gömülmenin sınırlı yüzleri kümesinin düzlemsel grafik için bir döngü temeli oluşturduğu sonucu çıkar: Sınırsız yüzün bu döngü dizisinden çıkarılması, her bir Euler alt grafiğinin ikiden tam olarak bire oluşturulma yollarının sayısını azaltır.

Mac Lane'in düzlemsellik kriteri

Adını Saunders Mac Lane'den alan Mac Lane'in düzlemsellik kriteri , düzlemsel grafikleri döngü uzayları ve döngü tabanları açısından karakterize eder. Sonlu bir yönsüz grafiğin, ancak ve ancak grafiğin, grafiğin her kenarının en fazla iki temel döngüye katıldığı bir döngü temeli varsa düzlemsel olduğunu belirtir. Düzlemsel bir grafikte, bir gömme işleminin sınırlı yüzler dizisi tarafından oluşturulan bir döngü temeli zorunlu olarak bu özelliğe sahiptir: her kenar yalnızca ayırdığı iki yüz için temel döngülere katılır. Tersine, bir döngü temeli kenar başına en fazla iki döngüye sahipse, döngüleri, grafiğinin düzlemsel gömülmesinin sınırlı yüzleri kümesi olarak kullanılabilir.

Dualite

Bir düzlemsel grafiğin döngü alanı , ikili grafiğin kesme alanıdır ve bunun tersi de geçerlidir. Bir düzlemsel grafiğin minimum ağırlık döngüsü temeli, sınırlanmış yüzleri tarafından oluşturulan temel ile aynı olmak zorunda değildir: yüz olmayan döngüleri içerebilir ve bazı yüzler, minimum ağırlık döngüsü temelinde döngüler olarak dahil edilmeyebilir. İki döngünün birbiriyle kesişmediği bir minimum ağırlık döngüsü temeli vardır: temeldeki her iki döngü için ya döngüler sınırlanmış yüzlerin ayrık alt kümelerini çevreler ya da iki döngüden biri diğerini çevreler. Döngü uzayları ve kesme uzayları arasındaki ikiliği takiben, düzlemsel grafiğin bu temeli , kesme alanı için minimum ağırlık temeli olan ikili grafiğin Gomory-Hu ağacına karşılık gelir .

Hiçbir yerde sıfır akış yok

Düzlemsel grafiklerde, farklı renklere sahip renklendirmeler , modulo tamsayılar halkası üzerinde sıfır akışa sahiptir . Bu dualitede, iki bitişik bölgenin renkleri arasındaki fark, bölgeleri ayıran kenar boyunca bir akış değeri ile temsil edilir. Özellikle, hiçbir yerde sıfır 4 akışının varlığı, dört renk teoremine eşdeğerdir . Snark teoremi düzlemsel olmayan grafiklere bu sonucu yaygınlaştırır. ${\ displaystyle k}$${\ displaystyle \ mathbb {Z} _ {k}}$${\ displaystyle k}$

Referanslar