Лекция 21: Введение в теорию графов. Способы представления ориентированных и неориентированных графов: матрицы смежности и инцидентности, списки инцидентностей;

Предлагается разделить (условно) терминологию теории графов на:

Одно и то же понятие теории графов тогда будет можно формулировать на трех "языках". Так, например, определение графа:

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

Теоретико-множественное - графом называется пара (V,R), где V – это множество вершин или узлов, R – это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами. Обозначается граф обычно через G(V,R).

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | R | — размером графа.

Вершины u и v называются концевыми вершинами (или просто концами) ребра r = . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Ребро называется петлёй, если его концы совпадают, то есть r = .

Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v ® w ведёт от вершины v к вершине w.

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

Ориентированным путём в орграфе называют конечную последовательность вершин vi (i=1,…,k), для которой все пары (vi,vi + 1) (i=1,…,k-1) являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Матричное - графом называется множество (класс) квадратных (0,1)-матриц, перестановочно подобных между собой.

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

Так на рисунке 1 даны два представления одного и того же графа.

Другое задание графа - списком. Можно считать, что в соответствии с теоретико-множественным определением графа все элементы множества RÍV´V, входящего в определение, упорядочены сначала по первым элементам пар, а затем по вторым, в соответствии с нумерацией вершин. Тогда два представления графа с рисунка 1 будут заданы двумя списками:

1 2, 3, 4 I II, III, V

В первом столбце - первые элементы пар, затем по строкам, списком через запятую, идут вторые элементы.

Третье задание графа - матрицами. Ниже выписаны две матрицы - A и B, задающие два представления графа с рисунка 1:



Дифференциал дуги


Узнать стоимость за 15 минут
  • Тип работы
  • Часть диплома
  • Дипломная работа
  • Курсовая работа
  • Контрольная работа
  • Реферат
  • Научно - исследовательская работа
  • Отчет по практике
  • Ответы на билеты
  • Тест/экзамен online
  • Монография
  • Эссе
  • Доклад
  • Компьютерный набор текста
  • Компьютерный чертеж
  • Рецензия
  • Перевод
  • Репетитор
  • Бизнес-план
  • Конспекты
  • Проверка качества
  • Единоразовая консультация
  • Аспирантский реферат
  • Магистерская работа
  • Научная статья
  • Научный труд
  • Техническая редакция текста
  • Чертеж от руки
  • Диаграммы, таблицы
  • Презентация к защите
  • Тезисный план
  • Речь к диплому
  • Доработка заказа клиента
  • Отзыв на диплом
  • Публикация статьи в Вак
  • Публикация статьи в Scopus
  • Дипломная работа MBA
  • Повышение оригинальности
  • Шрифт, pt
  • 12 pt
  • 14 pt
  • Другой
Прикрепить файл
Заказать