Тема 4.1. Основные понятия и операции на графах

Глава 4. Теория графов

Резюме по теме

Вопросы для повторения

1.Что такое разбиение?

2.Запишите полиномиальную формулу?

3.О чем говорится в теореме о полиномиальных коэффициентах?

4.Как выглядит формула включений и исключений?

5.Для чего необходима формула включений и исключений?

Рассмотрено понятие разбиения. Приведены необходимые теоремы разбиения. Показана полиномиальная формула, а так же приведена теорема о полиномиальных коэффициентах. Рассмотрены формулы включений и исключений.

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G={R,V}, где V есть подмножество любого счётного множества, а R - подмножество V×V.

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов «граф» или «сеть».

При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случаи ориентированного графа отрезки заменяют стрелками.

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать какие пары вершин соединены ребрами, а какие - нет. Часто на практике бывает трудно ответить на вопрос - являются ли два изображения моделями одного и того же графа, или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

Теория графов решает такие задачи как: семь мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736; проблема четырёх красок — была сформулирована в 1852 году, но доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)); задача коммивояжёра — одна из наиболее известных NP-полных задач; задача о клике — ещё одна NP-полная задача; нахождение минимального стягивающего дерева.

В настоящее время на языке теории графов формулируются и решаются многие задачи управления, в том числе задачи сетевого планирования и управления, анализа и проектирования организационных структур управления, анализа процессов функционирования и целеполагания, многие задачи принятия решений в условиях неопределенности и др.

Гипотеза Улама - а) всякий граф с более чем двумя вершинами однозначно определяется набором графов, где каждый граф из набора получен удалением одной из вершин исходного графа. б) всякий граф с более чем тремя вершинами однозначно определяется множеством графов, где каждый граф из множества получен удалением одной из вершин исходного графа. (Иными словами, не существует таких двух различных графов для которых бы эти наборы или множества совпадали).

Цель: ознакомиться с основными понятиями теории графов.

Задачи:

1. Рассмотреть основные понятия.

2. Ознакомиться со способами задания графов.

3. Изучить операции над частями графа.

4. Рассмотреть графы и бинарные отношения.

Рис. 4.1. Диаграммы: а) гистограмма, б) график, в) круговая и г) кольцевая.

Мощным и наиболее исследованным классов объектов, относящихся к графическим представлениям, являются так называемых графы. Теория графов имеет огромные приложения, так как ее язык, с одной стороны, нагляден и понятен, а с другой – удобен в формальном исследовании.

При изображении графа не все детали рисунка одинаково важны; в частности, несущественны геометрические свойства ребер (длина, кривизна и т.д.) и взаимное расположение вершин на плоскости.