Знайте, Intuit, лекция, презентация на планарна графика

Резюме: планарна графика. Homeomorphic графики. Формула на Ойлер. Триангулирана графика. Задачи.

планарна графика

Планарни графика е графика. изобразен на равнината, така че няма две от неговите краища (или по-скоро, техните представителни криви) не се пресичат геометрично навсякъде с изключение на инцидента, за да ги двата върха. Граф. изоморфни на равнината графика се нарича планарна. Planar графика може да се определи по-скоро като тази: графика е равнинна, ако той може да бъде пуснат на самолета. Чертеж графика, в която всеки два от ръбовете не се припокриват, с изключение на точките на пресичане общи върха, наречена плосък представяне на графиката. Ясно е, че плосък представяне има само планарна графика. Обратно, във всяка равнинна графика има сигурност планарна представяне. Равнинни графики - просто цикли, дървета, горски. както и Графа. съдържащ пръстен, от който върховете "излизат" дървета.

Пример. Пример за не-равнинна графика може да служи като пълен графика с пет върха. Всеки опит да се направи своя плосък представителство се превърне в провал.

Както характеристиките на плосък представяне на графиката представя концепцията на лицето. Edge в жилищна представяне на графика е тази част от равнината, ограничена от един прост цикъл и не се съдържа в други цикли.

Фигурата показва плоска представяне на графика с три лица: ,,. Част от равнината, ограничена от прост цикъл, лицето не е така, тъй като тя съдържа един цикъл. Обикновено цикъл. очертаващ лицето, наречена граница лицето. Две лица ще бъдат призовани съседни. ако техните граници да имат поне един общ ръб.

В тази част на графиката, ограничена от прост цикъл, лице, от ръба, разположен във вътрешността на лицето. Тя не образува примка.

Не е ли едно лице самолет излюпени част в този пример, защото тя се състои от един цикъл, а освен това тази част на самолета не е ограничен цикъл. Един ръб е мост между циклите. Тези мостове са наречени дялове.

Както лицата могат да се считат за част от равнината намира "извън" плоската представяне на графиката. Тя е ограничена до "вътре" прост цикъл и не съдържа други цикли. Тази част от равнината се нарича безкрайна лицето.

Фигурата на безкрайна лицето се затъмнява. Всеки апартамент има преброяване оглед не е безкраен лице. или тя има точно един безкраен край. Като специален случай, вход аспект на безкрайността в жилищна представителство на дървото и гората. В плосък представителството на дървото и гората за целия аспект равнината на фигурата.

Две графики са homeomorphic (или идентични до върховете на степен 2), ако и двете от тях може да бъде получена от същата графика "включване" в новите крайни върхове на степен 2.

Изобразени homeomorphic графики, и същото може да се каже, на всеки две циклични графики. Homeomorphic графики е съотношението на еквивалентност. Ясно е, че въвеждането на термина "homeomorphic" удобно само от техническа гледна точка - включването или отстраняването на върховете на степен 2, няма нищо общо с плоскостенността. Добавянето (включване) по един връх, да речем, някой ръб. например, както следва: Нека върховете и ръб е инцидент. След края се отстранява от графиката, но добавя две нови ръбове: инцидент и върхове и върхове и инциденти.