Wikipédia

„Élgráf” változatai közötti eltérés

Laptörténet interaktív böngészése
[ellenőrzött változat][ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Porribot (vitalap | szerkesztései)
botok
127 263 szerkesztés
Nincs szerkesztési összefoglaló
Címkék: Mobilról szerkesztett Mobil web szerkesztés
172. sor:
=== Mediális gráfok és konvex poliéderek ===
{{fő|Mediális gráf}}
Ha egy ''G'' [[síkgráf]] maximális [[fokszám (gráfelmélet)|fokszáma]] három, akkor élgráfja síkba rajzolható és ''G'' minden síkba illesztése kiterjeszthető ''L''(''G'') egy síkba illesztésére. A magasabb fokú síkgráfok közül azonban léteznek olyan, melyek élgráfjai nem síkgráfok. Ezek közé tartozik például a ''K''<sub>1,5</sub> csillaggráf, az ékkőgráf (<math>F_4F_{4,1}</math> legyezőgráf), mely egy szabályos ötszög két nem metsző átlójának berajzolásával kapható meg, valamint az összes [[konvex poliéder]], melynek maximális fokszáma 4 vagy több.<ref>{{harvtxt|Sedláček|1964}}; {{harvtxt|Greenwell|Hemminger|1972}}.</ref>
 
Egy alternatív konstrukció, a [[mediális gráf]] legfeljebb három fokszámú síkgráfok esetében egybeesik az élgráffal. Ugyanannyi csúcsa van, mint az élgráfnak, de potenciálisan kevesebb éle: a mediális gráf csúcsai akkor és csak akkor vannak éllel összekötve, ha a két él a síkbarajzolt gráf ugyanazon tartományában egymás után következik. Egy síkgráf [[duális gráf]]jának mediális gráfja megegyezik az eredeti gráf mediális gráfjával.<ref>{{citation
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Élgráf”