Позначений граф – граф, вершинам або дугам якого присвоєно будь-які мітки, наприклад, натуральні числа або символи якого-небудь алфавіту . Породжений підграф – підграф, породжений безліччю ребер вихідного графа. Містить не обов’язково всі вершини графа, але ці вершини з’єднані такими ж ребрами, як у графі.
Зміст
- 1.1 Простий граф
- 1.2 Псевдограф
- 1.3 Мультиграф
- 1.4 Псевдомультиграф
- 1.5 Орієнтований граф
- 1.6 Змішаний граф
- 1.7 Ізоморфні графи
- 1.8 Інші пов’язані визначення
Як уже було сказано, графи мають дуже широке застосування: за їхньою допомогою обирають найвигідніше розташування будівель, графами представлені схеми метро. Далі наведено деякі приклади застосування графів . 1. Можна скласти граф будь-якої позиційної гри: шахів, шашок, “хрестиків – нуликів”.
Граф називають повним, якщо він містить усі можливі для цього типу ребра за незмінної множини вершин. Так, у повному звичайному графі кожна пара різних вершин з’єднана рівно однією ланкою.