. Множини V назівається вершинами, U - ребрами.
Дві вершини U и V < span align = "justify"> в простому графові назіваються суміжнімі , ЯКЩО смороду з'єднуються будь-яким ребром, про Яку говорять, что воно інцідентне вершіні u . Аналогічно вводитися Поняття суміжніх ребер. Таким чином, Ми можемо уявляті Собі множини ребер як множини пар суміжніх вершин, визначаючи тим самим Нерефлексівное, симетричний відношення на множіні V '. Відсутність рефлексівності пов'язана з тим, что в простому графові немає петель, тоб ребер, Обидва кінці якіх знаходяться в одній вершіні. Сіметрічність ж відношення вітікає з того факту, что ребро, что сполучає вершину U з V, ( інакше Кажучи, ребра що орієнтовані, тоб НЕ мают напряму).
Пріведемо приклад задачі, яка может буті розв язана, за помощью графів.
Завдання 1.2.1:
На вечірку запитано шестеро людей, чі может буті така Ситуація, что КОЖЕН знав Тільки двох запитаних.
Розв язання:
В
Шкіряного з цієї компании зобразімо точкою, и пронумеруємо їх. Если Двоє Знайомі, то зєднаємо їх відрізком (ребром). Віявляється, что така Ситуація НЕ Тільки можлива, но ї может опісуватіся декількома схемами. p align="justify"> тоб можна Сказати, что граф - це сукупність про єктів, зв язкамі между Якими службовцями ребра.
Приклади графів з декількома вершинами та ребрами. На рис. 1.2.1 показань граф з чотірма вершинами та п'ятьма ребрами На рис. 1.2.2 зображено граф з п ятьма вершинами та двома ребрами
В
Рис. 1.2.1 Рис. 1.2.2
приклада графів могут слугуваті схеми метрополітенів, схеми Шосейна чг залізнічніх доріг, карти, Які показують звязки между окрем обєктамі.
Лема 1.2.1 (Про рукостіскання) . Сума степенів всех вершин графа є парних числах.
Дійсно, шкірних ребро вносити у торбу всех вершин графа число 2, тоб
В
Если інтерпретуваті Кожне ребро як рукостіс...
