Теория графов - Что это такое

Теория графов - Что это такое

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

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

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

Кружки — вершины графа

Линии со стрелками – дуги (можно двигаться только в направлении стрелки)

Без стрелок – рёбра (можно двигаться в обе стороны)

Пример графа

Обозначается как G (X,V)

X — множество вершин

V — множество связей

 

Части графа:

  • частичный граф — граф, содержащий всё вершины исходного графа и часть инцидентных им рёбер
  • подграф — граф, все вершины и рёбра которого содержаться среди вершин и рёбер исходного графа
  • частичный подграф — граф, содержащий часть вершин исходного графа и часть инцидентных им рёбер

 

Смежные вершины — вершины, соединённые дугой или ребром.

Концевые вершины — вершины, определяющие связь т.е. её начало и конец.

Смежные связи — рёбра (дуги), имеющие общую концевую вершину (присоединены к одной вершине).

Инцидентные — ребро (дуга) и её концевые вершины (связи и вершины, соединённые напрямую).

Вес ребра (дуги) — положительное (не нулевое) число, обозначающее дополнительные данные: фактическое расстояние/стоимость/время поездки и т.п.

Петля — связь, ведущая в ту же вершину, откуда вышла.

Кратные рёбра — все рёбра, соединяющие данные две вершины.

Кратные дуги — все дуги, имеющие одно начало и один конец.

 

Степень вершины — число рёбер, присоединяющихся к этой вершине.

Для ориентированного графа вычисляются две полустепени:

  • полустепень захода — кол-во дуг, заходящих в данную точку
  • полустепень исхода — кол-во дуг, исходящих из этой точки

 

Маршрут (путь) — последовательность смежных вершин (т.е. последовательность вершин, имеющая для каждой вершины связь, соединяющую её со следующей вершиной).

Длина маршрута — кол-во связей в нём (для взвешенного графа — сумма всех весов в данном маршруте).

Виды маршрутов:

  • цепь — путь, в котором нет повторяющихся связей
  • простая цепь — путь, в котором нет повторяющихся вершин
  • цикл — замкнутая цепь (конечная точка маршрута совпадает с начальной)
  • простой цикл — замкнутая простая цепь (конечная точка маршрута совпадает с начальной)

Особые виды маршрутов:

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

 

Изолированная вершина — вершина, не имеющая входных и выходных связей.

Висячая вершина — имеет только одну связь (входящую или выходящую).

 

Компонента связности — максимальный по включению вершин связный (сильно связный) подграф графа (другими словами — изолированная часть графа).

Степень связности (k) — общее число компонент связности

TEXT.RU - 46.46%

Поделиться ссылкой:

Добавить комментарий

Зарегистрируйтесь или Войдите, чтобы оставить комментарий.

Системное сообщение