дугами з іншими вершинами графа. p> Якщо дуга
U виходить з вершини
х або заходить у
х , то дуга
U називається инцидентной вершині
х , а вершини
х инцидентной дузі
U . Загальне число дуг, инцидентной вершині
х , є ступенем вершини
х Р (х) . Вершини, ступінь яких
Р (х)> 2 , називаються вузлом, а зі ступенем
Р (х) <2 - антіузлом.
полустепені заходу Р + (х) вершини х - кількість дуг, що заходять у дану вершину. Полустепені результату Р - (х) - кількість дуг, що виходять з даної вершини.
Послідовність ліній на графі
В
Шлях - послідовність дуг ( U 1 , U 2 , ... U n ), в якій кінець кожної попередньої дуги збігається з початком наступної. Шлях може бути кінцевим і нескінченним. p> Шлях називається простим, якщо в ньому ніяка дуга не зустрічається двічі, і складовим, якщо будь-яка з дуг зустрічається більше одного разу.
Шлях, в якому жодна з вершин не зустрічається більше одного разу, називається елементарним шляхом.
Гамильтонов шлях - шлях проходить через всі вершини, але тільки по одному разу,
Еллер шлях - шлях містить всі дуги графа, при цьому тільки по одному разу.
Довжина шляху - число дуг послідовності ( U 1 , U 2 , ... U n ).
Гілка - шлях, в якому початкова та кінцева вершини є вузлами. Дуга (x, y) називається замикає, якщо видалення її не приводить до анулювання шляху з x в y.
Контур - кінцевий шлях, починається і закінчується в одній і тій же вершині. Контур одиничної довжини називається петлею.
Орієнтований граф - граф, у якого вершини з'єднуються напрямними стрілками.
Графи можна розглядати з урахуванням або без урахування орієнтації його дуг.
Різновиди графів
В
Нуль-граф - граф (X, U) , складається тільки з ізольованих вершин.
Однорідний граф - якщо ступеня всіх вершин графа однакові і P + (x) = P - (x) = 0. p> симетричних граф - граф, в якому дві будь суміжні вершини з'єднані тільки двома протилежно орієнтованими дугами.
Антісімметріческій - граф, в якому кожна пара суміжних вершин з'єднана тільки в одному напрямку.
Повний - граф, в якому будь-яка пара вершин з'єднана однаковим числом дуг.
мультіграф - граф, в якому хоча б дві суміжні вершини з'єднані більш ніж однією дугою. Найбільше число дуг, що з'єднують суміжні вершини графа називається кратністю.
Підмножини графів <В
Подграфом графа G (X, U) називається граф G (A, U A ) , який визначається наступним чином:
1. Вершинами A подграфа G (A, U A ) є деяка підмножина вершин графа G...
