Наприклад, у вигляді графа можуть бути зображені:
- електричні і транспортні мережі;
- інформаційні і комп’ютерні мережі;
- карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;
- моделі кристалів;
- структури молекул хімічних речовин;
- моделі ігор;
- різні математичні об’єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);
- лабіринти;
- плани діяльності або плани виконання певних робіт (розклади);
- генеалогічні дерева тощо.
Приклади застосування теорії графів:
- пошук зв’язних компонентів у комунікаційних мережах;
- пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;
- побудова кістякового дерева: зв’язність з найменшою можливою кількістю ребер;
- пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;
- ізоморфізм графів: ідентичність структур молекул (ізометрія);
- знаходження циклів графів:
- гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);
- ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);
- розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;
- планарність графів: проектування друкованих електронних та електричних схем, транспортних розв’язок тощо;
- знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”).
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. Белов В.В. и др. Теория графов:учебное пособие для втузов.- М.: „Высшая школа”,1976. – 392 с.
2. Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979. – 143 с.
3. Гервер М. Трехзначные числа и орграфы // Журнал «Квант», Москва, МЦНМО, 1987, №2
4. Кузнецов О.П. Дискретная математика для инженеров. / О.П. Кузнецов, Г.М. Адельсон–Вельский – 2–е изд., перераб. и доп. – М.: Энергоатомиздат, 1988 – 400 с.: ил.
5. Мелихов А.Н. применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик – М.: Наука, 1974. 304 с.: ил.
6. Уилсон Р. Введение в теорію графов. – М.: Мир, 1777. – 208 с.
7. Оре О. Графы и их применение. – М.: Изд-во „Мир”, 1965.- 174 с.
8. Оре О. Теория графов. –2-е изд.- М.: „Наука”, 1980.- 205 с.
9. Уилсон Р. Введение в теорію графов. – М.: Мир, 1777. – 208 с.
10. Хаггарти Р Дискретная математика для программистов. – М.: «Техносфера», 2003. – 320 с.
11. Ядренко М.Й. Дискретна математика : навчальний посібник. – К.: Вид. – поліграф.центр „Експрес”, 2003. – 244 с.