Узагальненням графа є гіперграфах.
У гіперграфах, на відміну від графа, ребрами можуть бути не тільки двоелементні, а й будь-які підмножини вершин.
Подібні об'єкти у математиці відомі давно, однак введення терміну гіперграфах пов'язано з успішним розглядом на них ряду важливих понять і методів теорії графів.
Пустим називається граф без ребер. Повним називається граф, в якому кожні дві вершини суміжні. Граф називається зв'язковим, якщо для будь-яких двох вершин існує шлях, що з'єднує ці вершини. br/>
.1 Теореми
. Вершини графа називаються суміжними, якщо існує ребро, їх з'єднує.
. Два ребра G 1 і G 2 називаються суміжними, якщо існує вершина, інцідентная одночасно G 1 < span align = "justify"> і G 2 .
. Кожен граф можна у просторі безліччю точок, відповідних вершин, які з'єднані лініями, відповідними ребрах (або дугам - в останньому випадку напрямок зазвичай вказується стрілочками). - Таке уявлення називається укладанням графа ..
. Кінцева послідовність необов'язково різних ребер E 1 , E 2 , ... E n називається маршрутом довжини n, якщо існує послідовність V 1 , V 2 , ... V n необов'язково різних вершин, таких, що
E i = (V i-1 , V i ).
1. Якщо збігаються, то маршрут замкнутий.
2. Маршрут, в якому всі ребра попарно різні, називається ланцюгом.
3. Замкнуте маршрут, всі ребра якого різні, називається циклом. Якщо всі вершини ланцюга або циклу різні, то такий ланцюг або цикл називаються простими.
4. Цикл, в якому всі вершини, крім першої та останньої, попарно ...
