Studopediya

КАТЕГОРИЯ:


Лекция 10. изоморфизъм на графики. операции Графика

Съдържанието на лекции: графика изоморфизъм; подграфи на графиките и; операции на графиката; Примери на различни видове графики.

Лекция Цели: да разберете какво е понятието изоморфизъм за графики и как да го инсталирате; помисли за някои операции графиката и някои важни видове графики.

графика изоморфизъм

Една и съща графика, както е споменато по-горе, може да бъде представена чрез - различно. Например, Фигура 3.2.1 показва същата графика.


Фигура 3.2.1

Вижте списък на масиви и ребра зависи от номерацията на върхове и ръбове. Графики, различаващи се само при етикетирането на върхове и ръбове се наричат ​​изоморфни. Ние се даде точна дефиниция.

Определение. Две графики G 1 = (V 1, Е 1) и G 2 = (V 2, Е 2) са изоморфни (означен с G 1 ~ G 2), ако съществува Биекция φ: Запазването на съседство: д 1 = (U, V) д 2 = (φ (U), φ (V)) ,

Теорема. Изоморфизъм на графики е връзка равностойност.

Всъщност, всички изоморфизъм има свойствата на връзка еквивалентност: а) възвръщане (G ~ G); б) симетрия (G 1 ~ G 2 G 1 ~ G 2); в) преходен (G 1 ~ G 2, G 2 ~ G 3 G 1 ~ G 3).

Графиките са разгледани до изоморфизъм. Графика G 1 изоморфен на графика G е 2, ако и само ако съществуването на едно-към-едно кореспонденция между върховете на графиката, както и между техните краища. Понякога изоморфни графики могат да се видят в тяхното графично представяне. Например, графиките и на фигура 3.2.2 са изоморфни, защото достатъчно, за да се вдигне топ 3 в колоната до нивото на пика 2 и 4, и за обръщане на И това ще се види, че и Те имат една и съща форма.

Фигура 3.2.2

Помислете за създаване на общо правило на изоморфизъм на графики: а) да отчита броя на върховете (ако е различен, графиките не са изоморфни); б) запишете всички върховете на двете графики с техните градуса (за N-графики), или с чифт изходни правомощия и вход (за диграфът); в) за всеки връх на графиката се търси първия връх на втората графика за тяхната степен или степен на съвпадение на двойки, т.е. Ние се получи едно-към-едно кореспонденция между върховете на графиката (ако няма мач, графиките не са изоморфни). Почти един удобен върха на графиката разположен на върха на друга, както и от съответните върхове, свързани с линия.

Подграфи и на графиките

Opredelenie.Graf G 1 = (V 1, Е 1) е част от графика G = (V, E), ако 1 и E E; подграф G = (V, Е) се нарича част на G 1 = (V 1, Е 1), който притежава всички ръбове (дъги) отговарят в V 1. Фигура 3.11 показва графиката G, неговата подграф G 1 и G 2 част.

Фигура 3.2.3

<== Предишна лекция | На следващата лекция ==>
| Лекция 10. изоморфизъм на графики. операции Графика

; Дата: 01.15.2014; ; Прегледи: 176; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва! Най-новото допълнение , Al IP: 66.102.9.26
Page генерирана за: 0.046 сек.