Основни понятия от теория на графите

Тема 2.13. Основни понятия от теория на графите.

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






Ако ребрата са ориентирани, които обикновено показват, стрели. Те се наричат ​​дъги. и Графа с тези ребра се нарича насочено графика.
Ако краищата не са ориентирани. графика е ненасочена.

Графики обикновено са показани под формата на геометрични фигури, така че върха са представени с точки, а ръбовете - (. Фигура 2.15) от линии, свързващи точки.

Пантата е дъга, началната и крайната върха на който съвпадат.

Обикновено графика графика без линии и множество ръбове.

Vertex степен е два пъти броя на линии, които са в горната част на тази плюс сумата на останалите съседни ребра.

Нека е графика, без ръбове. Пълно е графика, в която всеки два върха са съседни.

, Път, вериги и цикли.

Път в насочено графика - е последователност от дъги, в която крайната върха на всяка дъга е различен от последния, е първоначалното връх на следващата.

v0 върховете, VN се наричат ​​свързани данни от (или свързани). Vertex v0 се нарича самото начало. VN - края на пътя. Ако V0 = VN, тогава пътят се нарича затворена. Броят п се нарича дължината на пътя.

Маршрутът в ориентирани дъги графика път, който може да бъде пренебрегната.
Верига маршрут, при което всички ребра са различни.
Цикъл затворен маршрут, който е верига.

Път, в който всички върхове са различни. нарича проста верига. Един цикъл, в който всички върхове с изключение на първия и последния ден. са различни. Това е прост цикъл.

Граф делимост отношения

Ние построи графика, показваща връзката на делимост в комплекта. Принципът е: ако от един номер на другата е верига, която води нагоре, докато второто число разделен на първа (Фигура 2.16.).

Подграф на графика, което е Подмодел на оригиналния графиката, т.е. подграф съдържа някои от първоначалните графиката върховете и някои ребра (само тези два края, които са включени в подграф).

ПОДГРАФ предизвикана от снимачната площадка на върха U е подграф с връх комплект - U. съдържащ тези и само тези ръбове, двата края на които са включени в U.

ПОДГРАФ се нарича обхващащ подграф, ако множеството от върховете съвпада с множеството от върховете на графиката.

Графиката е свързан. Ако всяка двойка върховете свързан.
Свързани компоненти на графика е подграф на графиката, чиито върхове са свързани.

Tree - един свързан граф без цикли.
Дърветата най-често се срещат в практиката в представителството на различни йерархии. Например, най-популярните семейни дървета.

Цифрата показва 2.17 библейския родословно дърво.

Граф гора, наречена без цикъл. Върховете на степен 1 ​​на едно дърво се наричат ​​листа.
Дървета - много удобен инструмент, предоставяне на информация от различни видове.
Дърветата са различни от прости графики, които са невъзможни цикъла при прекосяване на дървото. Това прави графена много удобен начин за организиране на данни за различни алгоритми. По този начин, концепцията на дървото се използва широко в компютърните науки и програмиране.

Очевидно е, че графичен начин за представяне на графики, неподходящи за PC. Поради това, има и други начини да представляват графики.

В графика прилага теория

intsindentsy матрица. Това е матрица с N реда, съответстващи на върховете и м колони sootvetstvuyuschngo ребрата. За насочено графика колона със съответния дъга (х, у) съдържа - 1 в ред, съответстващ на горната и х 1. в линия, съответстваща на у връх. Във всички останали 0. Loop, т.е. дъга (х, х) може да представлява различна стойност на х. Пример 2. Ако ненасочена графика, край на колоната sootvetstvuyushaya (х, у) са 1. съответното х и у и нули на всички други редове.

Матрицата за близост. Тази матрица на п х п където п - брой на върховете, където б у = 1. ако има ръб, ideschee от връх до връх х, у и б у = 0 в противен случай.

Intsindentnosti образува матрицата и съседство графиката за следващия непрекъснато (фиг. 2.18)