Графы
Автор: darya_leushkina • Июнь 8, 2018 • Реферат • 1,738 Слов (7 Страниц) • 769 Просмотры
Содержание
Введение 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 Деревья
Важным классом планарных графов являются деревья. Дерево – это связный граф, в котором нет циклов.
...