В някои приложения изискват разположени графика на двуизмерно повърхност (равнина, сфера, а многостен, на тор и т.н.), така че краищата на графиката не са кръстосани помежду си.
Определение. Наречен планарна графика, който може да бъде изобразен на самолета, така че ръбовете не се припокриват. Геометрична изображение на равнинна графика, в която ръбове не се пресичат, наречени равнинни графики.
ПРИМЕР 1 разгледаме примерите на графики и техните плоски плоски изображения:
Фигура 2.12. Примери за графиките и техните планарни плосък изображения
Всяка плоска графика, могат също да бъдат определени без да пресичат ръбове на областта или други видове повърхности. Критерият е равнинност на графики
Теорема 2.11. Pontryagin-Kuratowski.
Графика е равнинна, ако и само ако то не съдържа подграф homeomorphic графики K5 и K3,3.
Пример 2. За да се определи равнинност на графиката K4,4.
Решение. От графиката съдържа като K4,4 K3,3 подграф. След това теорема Pontryagin-Kuratowski, тя не е една и съща равнина.
Определение. Част от равнината, ограничена от планарни графика прост цикъл и не съдържа други върхове и ръбове, посочено лицето му. Цикъл ограничаване лицето, наречена граница лицето. Аспектите, в планарна графика, наречени вътрешни. изправят на външната страна на външно.
Всеки край на планарна графика принадлежи на точно две лица. отстраняването му води до факта, че двете лица се слеят в едно.
За планарни графики (pseudographs) притежава
Теорема 2.12. Формула на Ойлер. Ако п - брой на върховете, т - броя на ръбовете, г - брой ръбове на свързания планарна графика G. че
Забележка. Формула на Ойлер може да се прилага само за равнинни графики, които могат да бъдат разграничени от ръба.
Пример 3 Проверка на осъществимостта на формула dlyaploskogo Ойлер графика G = (V, X), V = (1, 2, 3, 4, 5, 6), X = ((1, 2), (1, 3), (1 , 4), (2, 3), (3, 4), (4, 5), (4, 6), (5, 6)) при ris.2.13.
Решение. Брой следните характеристики: п = 6, т = 8, г = 4 (3 вътрешни лица и един външен). Заместването формула Ойлер, ние получаваме: 4 + 6 - 2, = 8.
Пример 4. докаже, че графиката K5 не е равнинна.
Решение. Основни характеристики на графиката, както следва: п = 5, т = 5 ° 2 = (4 х 5) / (2 х 1) = 10. Ако приемем плоскостността под внимание на графиката, трябва да съществува плосък си образ. Тъй формула Ойлер намери броя на ръбове в равнината на изображението: R = 2 - п + т = 2 5 + 10 = 7. Тъй като всеки аспект на пълната графиката трябва да съдържа поне три ребра, общият брой на ръбове в лицата (включително повторения на преброяване) не трябва да бъде по-малко от 21. от единия край на планарна графика може да съдържа точно две лица, тогава общият брой ръбове не трябва да бъде по-малко от 11. обаче, m = 10.Otsyuda следва, че плоската подреждане графиката К5 съществува. Поради това, че не е една и съща равнина, както се изисква.
1. докаже, като се използва формула графика K3,3 не-плоскостността Ойлер.
2. Докажете, че графиката не е равнинен и K6 два начина
1) с помощта на теоремата Pontrjagin-Kuratowski-,
2) като се използва формула на Ойлер.
3. Проверете валидността на формулата на Ойлер за дървета.
4. Какъв е минималният брой на ръбове, за да бъдат отстранени от самолет графика, за да го превърне в едно дърво? Отговорът да се оправдае.
5. Възможно ли е да се изгради непланарна графика с 4 върха?
6. Изграждане на nonplanar графика с 6 върхове, които не съдържат K3,3.
7. Проверете плоскостенността на графиката K2,4.
8. Проверете куб плоскостността ПО 3.
9. Проверете куб плоскостността B 4.
10. Проверка на равнинност на графиката на Фигура 2.14.
Фигура 2.14. Граф Целева 10
СПРАВКА работно място, свързано
Свързани статии