Тема 4. графы и деревья. логические элементы компьютера

Понятие графа

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

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

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

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

 Деревья

Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

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

Если все вершины цикла разные, то такой цикл называется элементарным(или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

Путемв графе от одной вершины к другой называется

такая последовательность ребер, по которой можно проложить маршрут между этими вершинами.

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

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

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

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

Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:

Ст.вх.А=2, Ст.вых.А=1
Ст.вх.В=2, Ст.вых.В=0
Ст.вх.Д=1, Ст.вых.Д=3

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер

A1A2, A2A3, ..., Аn-1Аn в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.
На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути— простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды.
 
Ориентированным цикломназывается замкнутый путь в ориентированном графе.
На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

Так, на рисунке пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй - 3,
а третий — 4.