Застосування теорії графів

Граф є математичною моделлю найрізноманітніших об’єктів, явищ і процесів, що досліджуються і використовуються в науці, техніці та на практиці. Коротко опишемо найвідоміші застосування теорії графів, які мають хоча б мінімальне значення дотичне до політології.

Наприклад, у вигляді графа можуть бути зображені:

 транспортні мережі;

 інформаційні мережі;

 карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

 моделі ігор;

 генеалогічні дерева тощо.

Приклади застосування теорії графів:

 знаходження циклів графів (когнітивні карти):

 гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

 ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

 фарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо (політичні карти, геоінформаційні системи);

 знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”)

тощо.