Otomorfizmlerine göre tanımlanan grafik aileleri | ||||
---|---|---|---|---|
mesafe geçişli | → | normal mesafe | ← | kesinlikle düzenli |
↓ | ||||
simetrik (ark geçişli) | ← | t -geçişmeli, ( t ≥ 2) | simetrik sol (inç) | |
↓ | ||||
(bağlıysa) köşe geçişli ve kenar geçişli |
→ | normal ve kenar geçişli | → | kenar geçişli |
↓ | ↓ | ↓ | ||
üst geçişli | → | düzenli | → |
(iki taraflı ise) biregüler |
↑ | ||||
Cayley grafiği | ← | sıfır simetrik | asimetrik |
Olarak grafik teorisi , bir normal grafiktir bütün çıkıntılar komşu aynı sayıda, yani, aynı sahip bir grafiktir derecesi ya da valans. Köşeleri derece olan normal bir grafiğe normal grafik veya düzenli derece grafiği denir .
0-normal grafik, birbiriyle bağlantısı kesilmiş bir köşe kümesidir; 1-normal grafiğin çift sayıda köşesi vardır ve bir dizi bağlantısız veya birleşik kenarlardan oluşur ; son olarak, 2 düzenli grafik, bir dizi bağlantısız döngüdür . 3 düzenli grafiğe kübik grafik de denir .
0-normal grafik
1-normal grafik
2 düzenli grafik
Petersen grafiği (belirli kübik grafik)
2-düzenli sonsuz grafik
Oldukça düzenli bir grafik , her bitişik köşe çiftinin ortak olarak aynı sayıda komşuya sahip olduğu ve her bitişik olmayan köşe çiftinin aynı sayıda ortak komşuya sahip olduğu normal bir grafiktir . Çok düzenli olmayan en küçük grafikler , her ikisi de 6 köşeli döngü grafiği ve dolaşım grafiğidir . Tam grafik herkes için kuvvetle düzenlidir
Köşeleri olan düzenli bir grafiğin varlığı için gerekli ve yeterli bir koşul, eşit ve budur .
Crispin Nash-Williams'ın bir teoremi, köşeli herhangi bir normal grafiğin Hamilton döngüsünü kabul ettiğini belirtir .
Izin bitişik olması matris grafiği. Ancak ve ancak grafik düzenli bir bir özvektör arasında . Bir özvektör olduğunda, grafiğin derecesine eşit olan bir öz değere karşılık gelir.
Kendimizi normal grafikler sınıfıyla sınırlasak bile birçok grafik problemi zordur. Daha doğrusu, renklendirme , seyahat eden satıcı problemi ve maksimum kararlı problem , normal grafikler için ve hatta k sabitlenmiş k -düzenli grafikler için NP-zordur .
Öte yandan, grafiklerin izomorfizmi sorununa, örneğin düzenli grafikler gibi sınırlı dereceli grafiklerde polinom zamanda karar verilebilir.
GenReg yazılımı kullanılarak düzenli grafikler oluşturulabilir.