ожин: вершин V і ребер E, між якими визначено ставлення інцидентності. Кожне ребро e з E інцидентне рівно двом вершинам v ', v'', які воно з'єднує. При цьому вершина v 'і ребро e називаються інцидентними один одному, а вершини v 'і v'' називаються суміжними. Часто пишуть v ', v'' з G і e з G. Якщо | V (G) | = n, | E (G) | = m, то граф G є (n, m) граф, де n - порядок графа, m - розмір графа. br/>
Визначення
Ребро (v ', v'') може бути орієнтованим і мати початок (v ') і кінець (v'') (дуга в орграфе). p> Ребро (v, v) називається петлею (кінцеві вершини збігаються). p> Граф, що містить орієнтовані ребра (дуги), називається орграфом. p> Граф, що не містить орієнтовані ребра (дуги), називається Неограф. p> Ребра, інцідентние однієї парі вершин, називаються паралельними або кратними. p> Граф з кратними ребрами називається мультиграфом. p> Граф, що містить петлі (і кратні ребра), називається псевдографом. p> Кінцевий граф - число вершин і ребер звичайно. p> Порожній граф - безліч ребер пусто (число вершин може бути довільним). p> Повний граф - граф без петель і кратних ребер, кожна пара вершин з'єднана ребром. Позначення для повного графа з n вершинами - Kn. p> Граф називається дводольним, якщо існує таке розбиття безлічі його вершин на дві частини, що кінці кожного ребра належать різним частинам (часток). p> Якщо будь-які дві вершини дводольного графа, що входять в різні частки, суміжні, то граф називається повним дводольним. Позначення для повного дводольного графа з n і m вершинами - Kn, m. p> Локальна ступінь вершини - Число ребер їй інцідентних. У Неограф сума ступенів усіх вершин дорівнює подвоєному числу ребер (лема про рукостискання). Петля дає внесок, рівний 2 в ступінь вершини. p> Слідство 1 з леми про рукостискання. Довільний граф має парне число вершин непарного ступеня. p> Слідство 2 з леми про рукостискання. Число ребер у повному графі n (n-1)/2. p> У орграфе дві локальних ступеня вершини v: deg (v) + і deg (v) - (число ребер з початком і кінцем в v)
Графи рівні, якщо безлічі вершин і інцідентних їм ребер збігаються. p> Графи, що відрізняються тільки нумерацією вершин і ребер, називаються ізоморфними. p> Граф називається регулярним (однорідним), якщо ступені всіх його вершин рівні. br/>
Способи завдання графів
Матриця інцидентності A. По вертикалі вказуються вершини, по горизонталі - ребра. Aij = 1 якщо вершина i інцидентна ребру j, в іншому випадку aij = 0. Для орграфа aij = -1 якщо з вершини i виходить ребро j, aij = 1 якщо у вершину i входить ребро j. Якщо ребро - петля, то aij = 2. Список ребер. У першому стовпці ребра, у другому вершини їм інцідентние. Матриця суміжності - квадратна симетрична матриця. За горизонталі і вертикалі - всі вершини. Dij = число ребер, що з'єднує вершини i, j. Матриця Кірхгофа: bij = -1, якщо вершини i та j суміжні, bij = 0 якщо вершини i і j не суміжні, bii = deg (i). Сума елементів у кожному рядку і кожному стовпці матриці Кірхгофа дорівнює 0.
язність
Ставлення вершин графа В«існує маршрут, що зв'язує вершини В»є відношенням еквівалентності, що задає розбиття графа на компоненти зв'язності. Індекс розбиття - k. p> МАРШРУТИ, ЦЕПИ, ЦИКЛИ
Переміжна послідовність v1, e1, v2, e2, ..., en, vn +1 вершин і ребер графа така, що ei = vivi +1 (i = 1, n), називається маршрутом, що з'єднує вершини 1 і vn +1 (або (V1vn +1)-маршрутом). Очевидно, що для завдання маршруту в графі достатньо задати послідовність v1, v2, ..., vn +1. його вершин, або послідовність e1, e2, ..., en його ребер. p> Вершина v називається досяжною з вершини u, якщо існує (u, v)-маршрут. Будь-яка вершина вважається досяжною з себе самої. p> Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі його вершини, крім, можливо, крайніх, різні. Маршрут (1) називається циклічним, якщо v1 = vn +1. Циклічна ланцюг називається циклом, а циклічна проста ланцюг - простим циклом. Число ребер у маршруті називається його довжиною. Цикл довжини 3 часто називають трикутником. Довжина всякого циклу не менше трьох, якщо мова йде про простому графі, оскільки в такому графі немає петель і кратних ребер. Мінімальна з довжин циклів графа називається його обхватом. p> Маршрут - послідовність ребер, в яких кожні два сусідніх ребра мають загальну вершину. p> Маршрут, в якому початок і кінець збігаються - циклічний. p> Маршрут в Неограф, в якому всі ребра різні - ланцюг. p> Маршрут в орграфе, в якому всі дуги різні - шлях. p> Шлях, в якому початок і кінець збігаються - контур. p> Ланцюг з неповторяющимися вершинами - проста. p> Циклічний маршрут називається циклом, якщо він ланцюг і простим циклом, якщо цей ланцюг проста. p> Вершини пов'язані, якщо існує маршрут з однієї вершини в іншу. p> Зв'язаний граф - якщо все його вершини пов'язані. ...
