Planáris grafikonok
Néhány alkalmazott probléma esetén egy kétdimenziós felületre (síkra, golyóra, poliéderre, tóruszra stb.) Grafikonra van szükség úgy, hogy a grafikon élei nem metszenek egymással.
Definíció. A gráfot sík gráfnak nevezzük, amely egy síkban ábrázolható úgy, hogy a szélei nem metszenek egymással. A sík grafikon geometriai képe, melyben a szélei nem metszenek, sík grafikonnak nevezik.
1. példa. Nézze meg a sík grafikonok és lapos képeik példáit:
2.12. Példák a sík grafikonokra és lapos képükre
Minden sík grafikon elhelyezhető anélkül, hogy széleket átlépne egy gömbön vagy más típusú felületeken. A grafikonok síkosságának kritériuma
ELMÉLET 2.11. Pontryagin-Kuratowski.
A gráf sík, ha és csak akkor, ha nem tartalmaz homemorfikus szubgráfokat a K5 és K3,3 grafikonokhoz.
2. példa: Határozza meg a K4,4 grafikon síkságát.
A megoldás. Mivel a K4,4 grafikon K3,3-t tartalmaz szubgrafikus formában. akkor Pontryagin-Kuratowski tétele szerint nem sík.
Definíció. A sík egy részét, amelyet egy sík görbe egyszerű ciklusa határol, és amely nem tartalmaz más csúcsokat és széleket benne, az arca. Az arcot határoló ciklus az arc határa. A sík gráf belsejében lévő határokat belsőnek nevezik. A külső határ kívül van.
A lapos gráf minden éle pontosan két arcnak felel meg. Eltávolítása azt eredményezi, hogy a két arc egybeolvad.
A sík grafikonok (álszövegek) esetében van
ELMÉLET 2.12. Euler képlete. Ha n a csúcsok száma, m az élek száma, r az egyes síkbeli G gráf arcainak száma.
Megjegyzés. Az Euler-formula csak sík grafikonokra alkalmazható, amelyekben az arcok megkülönböztethetők.
3. példa: Az Euler-képlet érvényességét a G = (V, X), V = (1, 2, 3, 4, 5, 6), X = ((1,2), (1,3), (4, 5), (4, 6), (5, 6)), a 4, 4, 5, 6,
A megoldás. A grafikon jellemzői a következők: n = 6, m = 8, r = 4 (3 belső felület és egy külső felület). Az Euler-formula helyettesítésével 4 + 6 - 8 = 2 értéket kapunk.
4. példa. Bizonyítsuk be, hogy a K5 grafikon nem sík.
A megoldás. A grafikon fő jellemzői: n = 5, m = C 2 5 = (5 × 4) / (2 × 1) = 10. Feltételezve a szóban forgó grafikon síkságát, sík képének léteznie kell. Mivel a Euler formula megtalálják az élek száma a képsík: r = 2 - n + m = 2- 5 + 10 = 7. Mivel minden rétegére a teljes gráf tartalmaznia kell legalább három bordát, a teljes élek számát az arcok (beleértve ismétlődik számnak kell lennie. Mivel egy sík gráf egyik élének pontosan két oldala lehet, az élek teljes számának legalább 11-nek kell lennie. Mindazonáltal m = 10. Ebből következik, hogy a K5 grafikonnak nincs lapos lefektetése. Következésképpen nem sík jellegű, amit be kellett bizonyítani.
1. Bizonyítsuk be a K3.3 grafikon nemplanaritását Euler-képlet segítségével.
2. Bizonyítsuk be, hogy a K6 grafikon nem sík kétféleképpen
1) a Pontryagin-Kuratowski tétel használatával,
2) az Euler formula használatával.
3. Ellenőrizze az Euler-féle képletek érvényességét.
4. Mi a legkisebb számú élek, amelyeket el kell távolítani egy lapos grafikonról ahhoz, hogy azt egy fába fordítsa? A válasz indokolt.
5. Lehetőség van egy nemplanáris grafikon létrehozására 4 csúcsmal?
6. Hozzon létre egy olyan nemplanáris gráfot, amely 6 csúcsot tartalmaz, amely nem tartalmaz K3,3-ot.
7. Ellenőrizze a K2,4 grafikon síkságát.
8. Ellenőrizze, hogy a B kocka sík.
9. Ellenőrizze a kocka síkságát B 4.
10. Ellenőrizze, hogy a grafikon sík-e a 2.14.
Ábra 2.14. Számolja be a 10-es feladatot
ELLENŐRZÉSI FELADATOK