Теорията на графите е област от математиката, свързана с графите. Графът е абстрактно представяне на: определен брой точки, които са свързани с линии. Всяка точка обикновено се нарича връх (повече от една — върхове), а линиите се наричат ребра. Графите са инструмент за моделиране на взаимоотношения и връзки между обекти и се използват за намиране на решения на различни практически и теоретични проблеми.

Някои от тези въпроси са:

  • Как да намерим най-къс път между два върха?
  • Дали графът е свързан и какви са неговите свързани компоненти?
  • Как да построим минимално покриващо дърво, което свързва всички върхове с минимална обща тежест?
  • Има ли в графа цикъл (например Евлеров или Хамилтонов път)?
  • Как да оцветим върховете с минимален брой цветове, така че съседни върхове да нямат еднакъв цвят?
  • Как да намерим максимум поток между два възела или максимално съвпадение в двуделни графи?

Основни понятия

  • Върхове (vertices) — елементите или обектите на графа.
  • Ребра (edges) — връзките между върховете; могат да бъдат без насока (неориентирани) или с посока (ориентирани).
  • Степен (degree) — броят на ребрата, свързани с даден връх (при ориентиран граф: входяща и изходяща степен).
  • Път и дължина — последователност от върхове, свързани чрез ребра; дължината е броят ребра или сумата на тежестите при тегловни графи.
  • Цикъл — път, който започва и завършва в един и същ връх без повторение на ребра/върхове (според дефиницията).
  • Свързаност — неориентиран граф е свързан, ако има път между всяка двойка върхове; при ориентиран граф важат понятия като силно и слабо свързан.
  • Дърво — свързан ацикличен неориентиран граф; минимално свързаната структура.
  • Подграф — граф, образуван от подмножество от върхове и/или ребра на даден граф.
  • Мултиграф и пепел (loop) — мултиграф позволява множество ребра между едни и същи върхове; пепел е ребро от връх към себе си.
  • Представяния — матрица на съседство, списък на съседи и списък на ребра са стандартни начини за кодиране на графи в компютърни програми.

Често срещани типове графи

  • Ориентиран (директен) граф — ребрата имат посока.
  • Неориентиран граф — връзките са без посока.
  • Двуделен (бипартиден) граф — върховете могат да се разделят в две множества, като ребрата свързват само върхове от различни множества.
  • Планарен граф — може да се нарисува в равнината без пресичащи се ребра.
  • Пълен граф — всеки връх е свързан с всеки друг връх.
  • Кликa — множество от върхове, всяка двойка от които е свързана (подграф на пълен тип).

Класически алгоритми

  • BFS (Breadth‑First Search) — обхождане по нива; намира най-късите пъти (по брой ребра) в неетажни графи.
  • DFS (Depth‑First Search) — дълбочинно обхождане; използва се за проверка на свързаност, откриване на цикли и топологично сортиране.
  • Dijkstra — алгоритъм за най-къс път при неотрицателни тежести.
  • Bellman‑Ford — намира най-къс път и открива отрицателни цикли.
  • Floyd‑Warshall — всички известни най-къси пъти (за малки графи).
  • Kruskal и Prim — алгоритми за минимално покриващо дърво (MST).
  • Топологично сортиране — за ориентирани ациклични графи (DAG).
  • Kosaraju и Tarjan — откриване на силно свързани компоненти в ориентирани графи.
  • Edmonds‑Karp / Dinic — алгоритми за максимален поток (и минимален разрез).
  • Hungarian — намиране на максимално съвпадение/минимален разход за съвпадение в двуделни графи.

Типични проблеми и задачи

  • Намиране на най-къс път (Shortest path)
  • Минимално покриващо дърво (MST)
  • Намиране на максимален поток / минимален разрез
  • Проблем за пътуващия продавач (TSP) — оптимизационен и NP-труден проблем
  • Оцветяване на граф (graph coloring) — приложимо в разпределение на ресурси и планиране
  • Намиране на Евлеров или Хамилтонов път
  • Проверка за изоморфизъм между графи (Graph isomorphism)

Приложения

  • Компютърни мрежи и интернет — моделиране на връзки между устройства, маршрутизиране и оптимизация на трафика.
  • Социални мрежи — анализ на общности, влияние, препоръчителни системи и разпространение на информация.
  • Транспорт и логистика — планиране на маршрути, оптимизация на мрежи за доставки и обществен транспорт.
  • Биология и химия — взаимодействия между протеини, метаболитни пътища, представяне на молекули като графи.
  • Електронни схеми — анализ и оптимизация на вериги и платки.
  • Оперативни изследвания и планиране — задачи за съвпадение, разпределение и разписания.
  • Географски информационни системи (ГИС) — мрежи от пътища, навигация и пространствен анализ.
  • Криптография и теория на информацията — някои проблеми и структури се изучават чрез графи.

Бележки и препоръки за учене

  • Започнете с основни понятия и ръчно решаване на малки примери (обхождания, степени, прости пътища).
  • Практикувайте имплементация на представяния на графи (матрица на съседство, списъци) и алгоритми като BFS/DFS и Dijkstra.
  • Използвайте визуализации — графите се разбират по-лесно, когато се рисуват и анализират графично.
  • За по-напреднали теми (NP-пълнота, комбинаторни оптимизации) се запознайте с евристики и алгоритми за приближени решения.

Теорията на графите е широко поле с богати математически резултати и практически приложения. Разбирането на основните структури и алгоритми дава мощен инструментариум за моделиране и решаване на проблеми в много области на науката и инженерството.