Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Графы и деревья. Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно




Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между «началом» и «концом» ребра.

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

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

 

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

Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (например, ребро e7).

Граф без петель и параллель­ных ребер называется простым.

Если ребро ек определяется вершинами viи vj (будем обозначать этот факт следующим образом: еk = (vi, vj), то говорят, что ребро ек инцидентно вершинам vi и vj.

Граф G(E,U) называется конечным, если множество Е вершин конечно. Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколь­кими ребрами, то такой граф называется мультиграфом. Две верши­ны еi, еj ÎЕ называются смежными, если они соединены ребром. Чис­ло ребер, инцидентных данной вершине еi, называется локальной степенью этой вершины р(еi). Число ребер r графа G(E,U) определя­ется выражением

Множества вершин и ребер части графа являются подмножества­ми вершин и ребер исходного графа

Полным графом называется граф у которого каждая вер­шина соединена ребрами с остальными вершинами

Обязанность графов

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

Две вершины еi и еj называются связанными, если существует мар­шрут из еi в еj.

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

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



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

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


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал