Графи, їх вершини, ребра і дуги
Граф F (V, E) може бути зображений геометрично. Для цього деякі n точок тривимірного простору позначаються елементами безлічі вершин V і вершини vi і vj з'єднуються лінією, якщо vi. vj>Î Е. Геометричне зображення графа будемо називати діаграмою.
Приклад 3.1. Нехай V = v1, v2, v3, v4>, а елементами множини E є всі можливі безлічі виду vi. vj> при i, j = 1,2,3,4; i¹j. Діаграма графа наведена на рис. 3.1, а.
Нехай тепер безліч E = e1, e2. em> є деякий бінарне відношення на множині V (E ÍV'V). Тоді пара множин V і E називається орієнтованим графом (Орграф) F (V, E) з множиною вершин V і множиною ребер E.
Ребро орієнтованого графа називається дугою. Для дуги ek = (vi. Vj) вершина vi називається початковою. а vj - кінцевої .Інимі словами, ребро ek виходить з вершини vi і заходить у вершину vj. Як і в разі неорієнтованого ребра, дуга ekінцідентна вершин vi і vj. а вершини vi і vjінцідентни дузі ek. Вершини vi і vj також називають суміжними.
Ребро, у якого кінцеві точки співпадають, називається петлею.
Приклад 3.2. Нехай V =. Задамо на цій множині відношення
Діаграма графа наведена на рис. 3.1, б.
З наведених визначень графів слід, що в них відсутні кратні. або паралельні. ребра, що з'єднують одні і ті ж пари вершин. Крім того, в неорієнтованому графі не допускаються петлі. Однак іноді зручно зняти зазначені обмеження.
Граф, що містить кратні ребра називається мультиграфом. Граф, що містить петлі і (або) кратні ребра, називається псевдографом.
Два графа F і F * ізоморфні. якщо існує таке взаємно однозначне відповідність між множинами їх вершин V і V *, що вершини з'єднані ребрами в одному з графів тоді і тільки тоді, коли відповідні їм вершини з'єднані в іншому графі. Якщо ребра орієнтовані, то їх напрямки також повинні відповідати один одному. Все ізоморфні графи мають однакові властивості.
Вершина, що не инцидентная ніякому ребру, називається ізольованою. Граф, состоящійтолькоіз ізольованих вершин, називається нуль-графом (порожнім графом) і позначається через 0. Для нуль-графа безліч ребер - пусте: Е =Æ.
Іншим важливим окремим випадком є повний граф. в якому кожна вершина безлічі V з'єднана ребром з усіма іншими вершинами цього безлічі. В подальшому повний неорієнтований граф з n вершинами будемо позначати Kn .У орієнтованому повному графі для кожної пари вершин є два ребра: по одному в кожному напрямку.
Приклад. На рис. 3.1, а представлений граф K4.
Особливо важливий тип частин складають підграфи. Нехай V * Í V. Подграф F * (V *, E *) графа F - це така частина графа F (V. E), безліч ребер E * якого складають всі ребра графа F (V. E), обидва кінці яких лежать в V *.
Якщо V * = V. то підграф F * (V *, E *) збігається з F (V. E). В іншому випадку підграф F * (V *, E *) називається власним подграфом графа F * (V *, E *). Для одиничної вершини V * = а> підграф F * (V *, E *) складається з петель в а.
Приклад (рис. 3.3). Для графа 3.3, а граф 3.3, б є частиною, але не є подграфом, тоді як граф 3.3, в є для графа 3.3, а як частиною, так і подграфом.
Число неорієнтованих графів з n вершинами
Нехай є n вершин, позначених відповідно: v1. v2. vn. Підрахуємо кількість різних діаграм, які можна побудувати на цих вершинах. Максимальна кількість ребер в графі визначається кількістю способів, якими з n вершин можна вибрати дві: a = Сn 2. Для кожного ребра існує дві можливості: або його проводять, чи ні. Відповідно до правила твори в комбінаториці, кількість діаграм, а значить, і графів, дорівнює 2 a.
Число неорієнтованих графів з n вершинами і m ребрами
Нехай як і раніше є n вершин, позначених відповідно: v1. v2. vn. Графів з m ребрами стільки, скільки існує способів з усіх a = Сn 2 ребер вибрати m ребер, тобто Сa m.