Графы

Содержание

Введение        3

1 Определения        4

2 Деревья        6

3 Практическая часть        10

Заключение        13

Список использованных источников        14

Введение

Графы возникли в 18 веке, когда известный математик Леонард Эйлер пытался решить теперь уже классическую задачу о Кёнигсбергских мостах. В то время в Кёнигсберге было два острова, соединённых семью мостами с берегами реки и друг с другом. Задача состояла в том, чтобы осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда началась прогулка. Решая эту задачу, Эйлер изобразил Кёнигсберг в виде графа, отождествив его вершины с частями города, а рёбра – с мостами [2].

Важным классом графов являются деревья. В данной работе будут введены основные понятия о деревьях в графах; будет доказана теорема о том, когда граф является деревом; будут построены различные плоские изображения дерева, получающиеся при разных выборах корня; в практической части будут изображены все деревья с n ≤ 6 вершинами.

1 Определения

Пусть G = (V, α) – некоторый граф. Путем в этом графе называется последовательность ребер, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Путь, каждая вершина которого принадлежит не более, чем двум его ребрам, по определению, является простым. Если начальная и конечная вершины пути совпадают, то путь называется циклическим. Простой циклический путь называется циклом. Если простой путь не является циклом, в нем существуют вершины, принадлежащие только одному ребру этого пути. Таких вершин две, их называют концами пути, а сам путь – цепью, соединяющей указанные вершины.

Длиной пути в графе называется количество входящих в состав этого пути ребер [1].

Вершины u и v называются связанными, если в G существует проходящий через них путь [7].

Если вершины u и v связаны, то наименьшая из длин цепей, соединяющих u и v, называется расстоянием между этими вершинами.

Вершина u называется смежной с вершиной v, если u находится на расстоянии 1 от v.

Отношение связанности является эквивалентностью на множестве вершин графа. Классы этого отношения называются компонентами связности (или просто компонентами).

Граф с универсальным отношением связанности называется связным. Таким образом, граф связен тогда и только тогда, когда любые две его различные вершины могут быть соединены цепью [1].

Изображение графа называется плоским, если никакие два ребра в этом изображении не пересекаются. Графы, имеющие плоское изображение, называют планарными [3].

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

Вполне несвязным графом называется граф без рёбер.

Полный граф – неориентированный граф, в котором каждая пара различных вершин смежна [1].

Изоморфизмом графов G1 =  (V1, α1) и G2  = (V2, α2) называется биекция между множествами вершин графов f: V1 → V2 такая, что любые две вершины u и v графа G1 смежны тогда и только тогда, когда вершины f(u) и f(v) смежны в графе G2 [6].

Соединением двух графов G1 =  (V1, α1) и G2  = (V2, α2), не имеющих общих вершин, называется граф [pic 1]

2 Деревья

Важным классом планарных графов являются деревья. Дерево – это связный граф, в котором нет циклов.