Теория графов и ее применение в науке

Картинка

Основные понятия в теории графов

Теория графов– дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории. Одно из центральных понятий теории графов, опираясь на которое строятся другие понятия - понятие инцидентности.

Определение 1. Друг другу инцидентны две вершины графа, если они соединены ребром; вершина и ребро графа инцидентны, если вершина является началом или концом ребра.

Определение 2. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными

Определение 3. Степенью вершины называется число ребер, которым принадлежит вершина. Обозначение: p (A ) – степень вершины A .

Определение 4. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k .

Определение 5. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.

Определение 6. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским, или планарным.

Определение 7. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью .

Определение 8. Путем от A до X называется последовательность ребер, ведущая от A к X , такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Определение 9. Циклом называется путь, в котором совпадают начальная и конечная точка.

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

Определение 11. Длиной пути , проложенного на цикле, называется число ребер этого пути.

Определение 12. Две вершины A и B в графе называются связными (несвязными ), если в нем существует (не существует) путь, ведущий из A в B .

Определение 13. Граф называется связным , если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным .

Определение 14. Компонентой связности графа (или просто компонентой графа) называется максимальный (по включению) связный подграф графа . Другими словами, это подграф , порождённый множеством вершин, в котором для любой пары вершин в графе существует -цепь и для любой пары вершин , не существует -цепи.

Определение 15. Матрицей смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) называется квадратная матрица A размера n, в которой значение элемента аij равно числу рёбер из i-й вершины графа в j-ю вершину.

Определение 16. Матрицей инцидентности называется одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждой дуге ставится в соответствующем столбце: «−1» в строке вершины x и «1» в строке вершины y; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится «0».

Определение понятия «граф»

Граф – математический объект, совокупность объектов соединенных между собой связями. Иначе говоря, граф – это совокупность двух множеств: множества точек, которые называются вершинами, и множества ребер. Например, за множество вершин можно взять множество аэропортов, обслуживаемых некоторой авиакомпанией, а за множество рёбер взять регулярные рейсы этой авиакомпании между городами.

Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B ,C ,D . Иногда граф в целом будем обозначать одной заглавной буквой.

Виды графов

Дерево – связный ациклический граф. Связность означает наличие путей между каждой парой вершин. Ацикличность – отсутствие циклов и то, что между парами вершин имеется всего по одному пути. Название «дерево» выбрано из-за очевидных сходств с деревом – растением.

Ориентированный граф(орграф) – граф, ребрам которого присвоено направление

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

Смешанный граф - это граф, в котором некоторые ребра могут быть ориентированными, а некоторые – неориентированными. Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфные графы – несколько графов различающиеся лишь нумерацией вершин и ребер. Они могут отличаться графическим изображением и матрицей смежности и инцидентности. Чтоб убедиться, что два графа - это один и тот же граф, необходимо и достаточно установит взаимно однозначные соответствия между ними.

Условия при которых графы изоморфны: 1) Графы имеют одинаковое количество вершин и ребер. 2) Вершины графов имеют одинаковые степени(в них сходятся одинаковое количество ребер)

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

Эйлеров граф – граф, содержащий эйлеров цикл, проходящий через каждое ребро графа ровно по одному разу.

Полуэйлеров граф - граф, содержащий эйлеров путь(цикл) проходящий по всем дугам(ребрам) графа и при том только по одному разу

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

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

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

Нулевой граф - граф состоящий из «изолированных» вершин без ребер.