4.1: Визначення

Template:MathJaxLevin

Досліджуйте!

Які (якщо такі є) з наведених нижче графіків однакові?

Наведені вище графіки не позначені. Зазвичай ми думаємо про граф як про певний набір вершин. Які (якщо такі є) з наведених нижче графіків однакові?

Власне, всі графіки, які ми бачили вище, - це лише креслення графіків. Графік насправді абстрактний математичний об'єкт, що складається з двох множин$V$ і$E$ де набір 2-елементних підмножин$E$ Чи графіки нижче однакові чи різні?$V\text{.}$

Графік 1:

• $V = \{a, b, c, d, e\}\text{,}$
• $E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\text{.}$

Графік 2:

• $V = \{v_1, v_2, v_3, v_4, v_5\}\text{,}$
• $E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{.}$

Перш ніж приступити до вивчення графіків, нам потрібно узгодити, що таке графік. Хоча ми майже завжди думаємо про графіки як зображення (точки, з'єднані лініями), це досить неоднозначно. Чи повинні лінії бути прямими? Чи має значення, наскільки довгі лінії або наскільки великі точки? Чи можуть бути дві лінії, що з'єднують одну і ту ж пару точок? Чи може одна лінія з'єднати три точки?

Те, як ми уникаємо неясностей у математиці, полягає в тому, щоб надати конкретні та суворі визначення. Створення хороших визначень непросто, але це неймовірно важливо. Визначення є узгодженою відправною точкою, з якої виходять всі істини в математиці. Чи існує графік без ребер? Ми повинні подивитися на визначення, щоб побачити, чи це можливо.

Ми хочемо, щоб наше визначення було точним і однозначним, але воно також повинно погоджуватися з нашою інтуїцією щодо предметів, які ми вивчаємо. Це має бути корисним: ми могли б визначити графік як шестиногий ссавець, але це не дозволило б нам вирішити жодних проблем щодо мостів. Замість цього, ось (тепер) стандартне визначення графіка.

Визначення

Граф - це впорядкована пара,$G = (V, E)$ що складається з непорожньої множини$V$ (званої вершинами) і$E$ множини (званої ребрами) двоелементних підмножин$V\text{.}$

Дивний. Ніде в визначенні не йдеться про точки або лінії. З визначення, графік може бути

\ begin {рівняння*} (\ {a, b, c, d\},\ {a, b\},\ {a, c\},\ {b, c\},\ {b, d\},\ {c, d\}\}). \ end {рівняння*}

Тут ми маємо графік з чотирма вершинами (літерами$a, b, c, d$) і чотирма ребрами (парами$\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\})$).

Дивлячись на набори та набори 2-елементних наборів важко обробити. Саме тому ми часто малюємо уявлення про ці набори. Ми ставимо крапку вниз для кожної вершини, і з'єднати дві точки з лінією саме тоді, коли ці дві вершини є однією з 2-елементних підмножин в нашому наборі ребер. Таким чином, один із способів намалювати графік, описаний вище, полягає в наступному:

Однак ми могли б також намалювати графік по-іншому. Наприклад, будь-який з них:

Ми повинні бути обережними щодо того, що означає, що два графіки будуть «однаковими». Насправді, з огляду на наше визначення, це легко: чи рівні вершинні множини? Чи рівні набори країв? Ми знаємо, що означає, щоб множини були рівними, а графіки - це не що інше, як пара двох спеціальних наборів.

Приклад$\PageIndex{1}$

Чи рівні наведені нижче графіки?

\ begin {рівняння*} G_1 = (\ {a, b, c\},\ {a, b\},\ {b, c\}\});\ qquad G_2 = (\ {a, b, c\},\ {a, c\},\ {c, b\}\})\ кінець {рівняння*}

рівний?

Рішення

Ні. Тут набори вершин кожного графа рівні, що є хорошим початком. Також обидва графіки мають два ребра. У першому графіку ми маємо ребра$\{a,b\}$ and $\{b,c\}\text{,}$ while in the second graph we have edges $\{a,c\}$ and $\{c,b\}\text{.}$ Now we do have $\{b,c\} = \{c,b\}\text{,}$ so that is not the problem. The issue is that $\{a,b\} \ne \{a,c\}\text{.}$ Since the edge sets of the two graphs are not equal (as sets), the graphs are not equal (as graphs).

Навіть якщо два графіки не рівні, вони можуть бути в основному однаковими. Графіки в попередньому прикладі можна намалювати так:

Графіки, які в основному однакові (але, можливо, не рівні), називаються ізоморфними. Точне визначення цього терміна ми дамо після короткого прикладу:

Приклад$\PageIndex{2}$

Розглянемо графіки:

• $G_1 = \{V_1, E_1\}$де$V_1 = \{a, b, c\}$ і$E_1 = \{\{a,b\}, \{a,c\}, \{b,c\}\}\text{;}$
• $G_2 = \{V_2, E_2\}$де$V_2 = \{u,v,w\}$ і$E_2 = \{\{u,v\}, \{u,w\}, \{v,w\}\}\text{.}$

Чи однакові ці графіки?

Рішення

Два графіки НЕ рівні. Досить помітити, що$V_1 \ne V_2$ since $a \in V_1$ but $a \notin V_2\text{.}$ However, both of these graphs consist of three vertices with edges connecting every pair of vertices. We can draw them as follows:

Зрозуміло, що ми хочемо сказати, що ці графіки в основному однакові, тому, хоча вони не рівні, вони будуть ізоморфними. Причина в тому, що ми можемо перейменувати вершини одного графа і отримати другий граф в результаті.

Інтуїтивно, графіки ізоморфні, якщо вони в основному однакові, або ще краще, якщо вони однакові, за винятком імен вершин. Щоб зробити поняття перейменування вершин точним, наведемо наступні визначення:

Ізоморфні графіки

Ізоморфізм між двома графами$G_1$ and $G_2$ is a bijection $f:V_1 \to V_2$ between the vertices of the graphs such that if $\{a,b\}$ is an edge in $G_1$ then $\{f(a), f(b)\}$ is an edge in $G_2\text{.}$

Two graphs are isomorphic if there is an isomorphism between them. In this case we write $G_1 \isom G_2\text{.}$

An isomorphism is simply a function which renames the vertices. It must be a bijection so every vertex gets a new name. These newly named vertices must be connected by edges precisely if they were connected by edges with their old names.

Example $\PageIndex{3}$

Decide whether the graphs $G_1 = \{V_1, E_1\}$ and $G_2 = \{V_2, E_2\}$ are equal or isomorphic.

• $V_1 = \{a,b,c,d\}\text{,}$ $E_1 = \{\{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\}$
• $V_2 = \{a,b,c,d\}\text{,}$ $E_2 = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$

Solution

The graphs are NOT equal, since $\{a,d\} \in E_1$ but $\{a,d\} \notin E_2\text{.}$ However, since both graphs contain the same number of vertices and same number of edges, they might be isomorphic (this is not enough in most cases, but it is a good start).

We can try to build an isomorphism. How about we say $f(a) = b\text{,}$ $f(b) = c\text{,}$ $f(c) = d$ and $f(d) = a\text{.}$ This is definitely a bijection, but to make sure that the function is an isomorphism, we must make sure it respects the edge relation. In $G_1\text{,}$ vertices $a$ and $b$ are connected by an edge. In $G_2\text{,}$ $f(a) = b$ and $f(b) = c$ are connected by an edge. So far, so good, but we must check the other three edges. The edge $\{a,c\}$ in $G_1$ corresponds to $\{f(a), f(c)\} = \{b,d\}\text{,}$ but here we have a problem. There is no edge between $b$ and $d$ in $G_2\text{.}$ Thus $f$ is NOT an isomorphism.

Not all hope is lost, however. Just because $f$ is not an isomorphism does not mean that there is no isomorphism at all. We can try again. At this point it might be helpful to draw the graphs to see how they should match up.

Крім того, зверніть увагу, що в$G_1\text{,}$ the vertex $a$ is adjacent to every other vertex. In $G_2\text{,}$ there is also a vertex with this property: $c\text{.}$ So build the bijection $g:V_1 \to V_2$ by defining $g(a) = c$ to start with. Next, where should we send $b\text{?}$ In $G_1\text{,}$ the vertex $b$ is only adjacent to vertex $a\text{.}$ There is exactly one vertex like this in $G_2\text{,}$ namely $d\text{.}$ So let $g(b) = d\text{.}$ As for the last two, in this example, we have a free choice: let $g(c) = b$ and $g(d) = a$ (switching these would be fine as well).

Ми повинні перевірити, що це дійсно ізоморфізм. Це, безумовно, біекція. Треба переконатися, що краю дотримуються. Чотири краю в$G_1$ are

\ begin {рівняння*}\ {a, b\},\ {a, c\},\ {a, d\},\ {c, d\}\ end {рівняння*}

Під запропонований ізоморфізм ці стають

\ begin {рівняння*}\ {g (a), g (b)\},\ {g (a), g (c)\},\ {g (d)\},\ {g (c), g (d)\}\ кінець {рівняння*}\ почати {рівняння*}\ {c, d\},\ {c, b\}, {c, b\}, {c, a\},\ {b, a\}\ end {рівняння*}

які є саме краями в$G_2\text{.}$ Thus $g$ is an isomorphism, so $G_1 \cong G_2$

Іноді ми будемо говорити про графік зі спеціальною назвою (як$K_n$ або граф Петерсона) або, можливо, намалюємо графік без будь-яких міток. У цьому випадку ми дійсно маємо на увазі всі графіки ізоморфні до будь-якої копії цього конкретного графа. Колекцію ізоморфних графіків часто називають класом ізоморфізму. ¹ Це не схоже на геометрію, де ми могли б мати більше однієї копії певного трикутника. Там замість ізоморфних ми говоримо конгруентний.

Існують інші зв'язки між графіками, про які ми дбаємо, крім рівності та ізоморфності. Наприклад, порівняйте наступні пари графіків:

Вони, безумовно, не ізоморфні, але зверніть увагу, що графік праворуч виглядає так, як це може бути частиною графіка зліва, особливо якщо ми намалюємо його так:

Ми хотіли б сказати, що менший графік є підграфом більшого.

Слід дати ретельне визначення цьому. Насправді існує два розумні поняття про те, що повинна означати підгрупа.

Підграфи

Ми говоримо, що$G_1 = (V_1, E_1)$ це підграф$G_2 = (V_2, E_2)$ наданих$V_1 \subseteq V_2$ і$E_1 \subseteq E_2\text{.}$

Ми говоримо, що$G_1 = (V_1, E_1)$ є індукованим підграфом$G_2 = (V_2, E_2)$ наданого$V_1 \subseteq V_2$ і$E_1$ містить всі ребра$E_2$ якого є підмножинами$V_1\text{.}$

Зверніть увагу, що кожен індукований підграф також є звичайним підграфом, але не навпаки. Подумайте про підграф як результат видалення деяких вершин і ребер з більшого графа. Щоб підграф був індукованим підграфом, ми все ще можемо видалити вершини, але тепер ми видаляємо лише ті ребра, які включали видалені вершини.

Приклад$\PageIndex{4}$

Розглянемо графіки:

Тут обидва$G_2$ і$G_3$ є підграфами$G_1\text{.}$ Але тільки$G_2$ є індукованим підграфом. Кожне ребро в$G_1$, що$G_2$ з'єднує вершини в також ребро$G_2\text{.}$ в$G_3\text{,}$ ребро$\{a,b\}$ знаходиться в,$E_1$ але не$E_3\text{,}$ навіть якщо вершини$a$ і$b$ знаходяться в$V_3\text{.}$

Графік НЕ$G_4$ є підграфом,$G_1\text{,}$ хоча це виглядає як все, що ми зробили, це видалити вершину$e\text{.}$ Причина в тому, що у$E_4$ нас є ребро,$\{c,f\}$ але це не елемент$E_1\text{,}$ тому у нас немає необхідного$E_4 \subseteq E_1\text{.}$

Повернутися до деяких основних визначень теорії графів. Зверніть увагу, що всі графіки, які ми намалювали вище, мають властивість, що жодна пара вершин не пов'язана більше одного разу, і жодна вершина не пов'язана з собою. Такі графіки іноді називають простими, хоча ми будемо просто називати їх графіками. Це тому, що наше визначення для графа говорить, що ребра утворюють набір 2-елементних підмножин вершин. Пам'ятайте, що немає сенсу говорити, що набір містить елемент більше одного разу. Таким чином, жодна пара вершин не може бути з'єднана ребром більше одного разу. Крім того, оскільки кожне ребро має бути набором, що містить дві вершини, ми не можемо мати єдину вершину, пов'язану з собою ребром.

Тим не менш, є випадки, коли ми хочемо розглянути подвійні (або більше) краю і один край петлі. Наприклад, «графік», який ми намалювали для проблеми Мостів Кенігсберга, мав подвійні краї, оскільки насправді є два мости, що з'єднують певний острів з найближчим берегом. Ми будемо називати ці об'єкти мультиграфами. Це гарна назва: мультимножина - це набір, в який нам дозволяється включати один елемент кілька разів.

Наведені вище графіки також пов'язані: ви можете перейти від будь-якої вершини до будь-якої іншої вершини, слідуючи деякому шляху ребер. Графік, який не пов'язаний, можна розглядати як дві окремі графіки, намальовані близько один до одного. Наприклад, наступний графік НЕ пов'язаний, оскільки немає шляху від$a$ до$b\text{:}$

Більшу частину часу має сенс розглядати незв'язані графіки як окремі графіки (розглядайте вищевказаний графік як два квадрати), тому якщо не вказано інше, ми будемо вважати, що всі наші графіки пов'язані.

Вершини графа не завжди мають ребра між ними. Якщо скласти всі можливі ребра, то отриманий графік називається завершеним. Тобто граф є повним, якщо кожна пара вершин з'єднана ребром. Оскільки граф визначається повністю тим, які вершини примикають до яких інших вершин, існує лише один повний граф із заданою кількістю вершин. Ми даємо їм особливу назву:$K_n$ це повний граф по$n$ вершинам.

Кожна вершина в$K_n$ примикає до$n-1$ інших вершин. Ми називаємо кількість ребер, що виходять із заданої вершини, ступенем цієї вершини. Таким чином, кожна вершина в$K_n$ має ступінь$n-1\text{.}$ Скільки ребер$K_n$ має? Можна подумати, що відповідь повинна бути,$n(n-1)\text{,}$ оскільки ми підраховуємо$n-1$ краї$n$ разів (один раз для кожної вершини). Однак кожне ребро падає на 2 вершини, тому ми порахували кожне ребро рівно двічі. Таким чином, є$n(n-1)/2$ ребра в$K_n\text{.}$ Альтернативний варіант, ми можемо сказати, що є${n \choose 2}$ ребра, оскільки, щоб намалювати ребро, ми повинні вибрати 2$n$ вершини.

Загалом, якщо ми знаємо градуси всіх вершин у графі, ми можемо знайти кількість ребер. Сума ступенів всіх вершин завжди буде подвоєною кількістю ребер, так як кожне ребро додає до ступеня двох вершин. Зверніть увагу, це означає, що сума ступенів всіх вершин у будь-якому графі повинна бути парною!

Приклад$\PageIndex{5}$

На недавньому математичному семінарі 9 математиків привітали один одного рукостисканнями. Чи можливо, що кожен математик потиснув руку рівно 7 людям на семінарі?

Рішення

Здається, що це повинно бути можливим. Кожен математик вибирає одну людину, з якою не тиснути руку. Але цього не може статися. Ми запитуємо, чи може граф з 9 вершинами мати кожну вершину ступінь 7. Якби такий граф існував, сума ступенів вершин була б$9\cdot 7 = 63\text{.}$ This would be twice the number of edges (handshakes) resulting in a graph with $31.5$ edges. That is impossible. Thus at least one (in fact an odd number) of the mathematicians must have shaken hands with an even number of people at the seminar.

Одне остаточне визначення: ми говоримо, що граф є двороздільним, якщо вершини можна розділити на дві$B\text{,}$ множини,$A$ і без двох вершин у$A$ сусідніх і не має двох вершин у$B$ сусідніх. Вершини в$A$ можуть бути сусідами з деякими або всіма вершинами в$B\text{.}$ Якщо кожна вершина в$A$ сусідній з усіма вершинами,$B\text{,}$ то граф є повним двороздільним графом і отримує спеціальну назву:$K_{m,n}\text{,}$ де$|A| = m$ і$|B| = n\text{.}$ граф в будинки та комунальні послуги головоломка$K_{3,3}\text{.}$

Названі графіки

Деякі графіки використовуються більше, ніж інші, і отримують особливі назви.

• $K_n$: Повний графік по$n$ вершинам.
• $K_{m,n}$: Повний двосторонній граф з множинами$m$ і$n$ вершинами.
• $C_n$: Цикл по$n$ вершинам, лише один великий цикл.
• $P_n$: Шляхи по$n$ вершинам, лише один довгий шлях.

Існує багато визначень, які слід відстежувати в теорії графів. Ось глосарій термінів, які ми вже використовували і незабаром зіткнемося.

Визначення теорії графів

• Graph: колекція вершин, деякі з яких з'єднані ребрами. Точніше, пара множин$V$ і$E$ де$V$ - набір вершин і$E$ являє собою набір 2-елементних підмножин$V\text{.}$
• Суміжні: Дві вершини є суміжними, якщо вони з'єднані ребром. Два ребра є суміжними, якщо вони мають спільну вершину.
• Двороздільний граф: граф, для якого можна розділити вершини на дві неспільні множини таким чином, щоб між будь-якими двома вершинами в одному множині не було ребер.
• Повний двороздільний граф: Двочастковий граф, для якого кожна вершина у першій множині прилягає до кожної вершини другого набору.
• Повний граф: граф, в якому кожна пара вершин є суміжною.
• З'єднано: граф з'єднується, якщо є шлях від будь-якої вершини до будь-якої іншої вершини.
• Хроматичне число: мінімальна кількість кольорів, необхідних для правильного фарбування вершин графіка.
• Цикл: шлях (див. Нижче), який починається і зупиняється на одній вершині, але не містить інших повторюваних вершин.
• Ступінь вершини: кількість ребер, що потрапляють на вершину.
• Euler шлях: прогулянка, яка використовує кожен край рівно один раз.
• Схема Ейлера: шлях Ейлера, який починається і зупиняється на одній вершині.
• Мультиграф: Мультиграф схожий на граф, але може містити декілька ребер між двома вершинами, а також окремі реберні петлі (тобто ребро від вершини до себе).
• Планарний: графік, який можна намалювати (у площині) без перетину країв.
• Підграф: Ми говоримо, що$H$ це підграф,$G$ якщо кожна вершина і ребро також$H$ є вершиною або ребром$G\text{.}$ Ми говоримо, що$H$ це індукований підграф,$G$ якщо кожна вершина$H$ є вершиною$G$ і кожна пара вершин в$H$ є сусідами в $H$якщо і тільки в тому випадку, якщо вони є сусідами в$G\text{.}$
• Дерево: (зв'язаний) графік без циклів. (Незв'язаний графік без циклів називається лісом.) Вершини в дереві зі ступенем 1 називаються листям.
• Забарвлення вершин: Призначення кольорів кожній з вершин графа. Забарвлення вершин є правильним, якщо сусідні вершини завжди пофарбовані по-різному.
• Прогулянка: Послідовність вершин, така, що послідовні вершини (у послідовності) є суміжними (у графі). Прогулянка, при якій не повторюється жодна вершина, називається простою