Прямим твором графів і називається граф, у якого (тобто вершини мають вигляд де причому
з'єднані ребром в точності в наступних випадках: а) б)
Наприклад, якщо то графом буде трикутна призма (див. Рис. 3.5).
Для графічної побудови графа слід намалювати граф а потім кожну з вершин "роздути" до графа
Вправа 3.5. зобразити граф
Рішення (див. Рис. 3.6).
Намалюємо граф з вершинами великого розміру - для того, щоб замінити кожну з них графом З'єднання вершин здійснюється за правилом (3).
Граф (п -мірний куб). Його вершинами є рядки де або 1. Дві вершини і з'єднані ребром в тому і тільки тому випадку, якщо рядки і мають відміну рівно в одній позиції, тобто існує таке що і при На малюнку 3.7 зображені графи і
Для спрощення позначень в запису вершин ми не пишемо дужки і коми, тобто пишемо 110 замість
Вправа 3.6. Знайти кількість вершин і ребер графа
Рішення. Так як вершини графа - це рядки і то всього вершин Далі, для вершини можна отримати суміжних з нею вершин, змінюючи по черзі кожну компоненту на протилежну Отже, з кожної вершини виходить рівно ребер. Значить, загальна кількість ребер дорівнює (поділ на 2 робиться з огляду на те, що інакше кожне ребро було б підраховано двічі). Отже,
Подграф. Зв'язний граф. Компоненти зв'язності графа
Нехай - граф. Поняття подграфа має два різні не еквівалентних між собою визначення.
Подграф в широкому сенсі графа - це граф де
Подграф у вузькому сенсі - це граф де і
Іншими словами, для побудови у графа подграфа в широкому сенсі треба виділити якесь безліч вершин і деякі з них з'єднати ребрами, взятими з графа Для отримання подграфа у вузькому сенсі треба взяти будь-яке безліч вершин і з'єднати їх в точності тими ребрами, якими вони з'єднувалися в графі На малюнку 8 зображено графи і такі, що - підграф графа в широкому, але не у вузькому сенсі. Щоб отримати з нього підграф у вузькому сенсі, слід додати ребро
Далі словом "підграф" ми будемо називати підграф в широкому сенсі.
Граф називається зв'язковим. якщо для будь-яких двох його вершин і існує шлях з в Будемо вважати, що з в завжди існує шлях нульової довжини (якщо довжину визначати за кількістю ребер). Будь-граф є об'єднанням своїх зв'язкових подграфов таких, що не існує ребер (а значить, і шляхів), що з'єднують вершини з різних Ці підграфи називаються компонентами зв'язності графа
Наприклад, граф зображений на малюнку 3.9, складається з трьох компонент зв'язності.
У зв'язкового графа