Тема 21. Графы, их способы задания

Граф – огромное количество точек (вершин графа), часть из которых соединена линиями (ребрами графа).

Ребро, соединяющее верхушку с ней же, именуется петлей.

Если верхушки соединяются направленными линиями (дугами графа), то граф именуют нацеленным (орграфом).

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

Если граф направленный, то одна из вершин дуги является исходной, а 2-ая – конечной.

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

Простые характеристики степеней вершин графа:

1. Сумма степеней вершин графа Тема 21. Графы, их способы задания равна удвоенному числу его ребер.

2. Число вершин нечетной степени четно.

Верхушка, не инцидентная никакому ребру, именуется изолированной.

Граф, состоящий только из изолированных вершин, именуется пустым либо нуль-графом.

Граф именуется полным, если любые две его верхушки являются смежными.

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

Маршрут (путь) – чередующаяся последовательность вершин и ребер, в какой каждые два примыкающих элемента инцидентны.

Количество ребер при всем этом именуется длиной маршрута.

Цепь – маршрут, в каком все ребра различны.

Обычная цепь – цепь, в какой все верхушки различны.

Цикл (обычный цикл Тема 21. Графы, их способы задания) – замкнутая (обычная) цепь.

Граф именуется связным, если для всех 2-ух его вершин найдется соединяющий их маршрут. Если хотя бы для одной пары вершин это свойство не производится, то граф именуется бессвязным.

Цикл, проходящий через все ребра графа ровно один раз, именуется эйлеровым, а граф, его содержащий, - эйлеровым графом. Связный граф Тема 21. Графы, их способы задания является эйлеровым и тогда только тогда, когда все его верхушки четной степени.

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

Дерево – связный граф без циклов.

Корневое дерево – дерево, в каком выделена одна из вершин (корень).

Методы задания графа:

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

2. Аналитический: представляется описание множеств и , потому что граф может быть определен как совокупа 2-ух множеств: , элементы которого именуются верхушками, и - случайное огромное количество пар , элементы которого именуются дугами.

3. Матричный: употребляются матрицы графов.

Матрица смежности Тема 21. Графы, их способы задания неориентированного графа - квадратная матрица порядка , где - количество вершин. Ее элементы равны числу ребер, соединяющих верхушки и .

Пример 1.В поселке 6 стационарных телефонов. Можно ли любой из их соединить кабелем ровно с 3-мя другими? Поменяется ли ответ, если добавить очередной телефон?

Решение: Построим граф, верхушки которого будут соответствовать телефонам Тема 21. Графы, их способы задания, а ребра – проводам, их соединяющим. По условию задачки каждый телефон должен быть соединен ровно с 3-мя другими. Соединим каждую верхушку графа ровно с 3-мя другими, к примеру, так, как показано на рис. 1.

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

Рис. 1

Пример 2.Меж городками A Тема 21. Графы, их способы задания, B, C, D, E, F, G, H скооперировано автобусное сообщение по последующей схеме: A-B, A-C, A-D, B-C, D-C, C-E, F-G, F-H, G-H. Найти, можно ли доехать на рейсовом автобусе из городка А в город Е и G. Если Тема 21. Графы, их способы задания да, то найти маршрут с минимальным числом пересадок.

Решение: Построим граф с верхушками, надлежащими городкам. Соединим ребром те верхушки, которые соответствуют городкам с автобусным сообщением. В итоге получен граф, состоящий из 2-ух связных подграфов, меж которыми нет ни 1-го маршрута.

Из рисунка видно, что проехать из городка А в Тема 21. Графы, их способы задания город Е можно 3-мя маршрутами: A-B-C-E, A-C-E, A-D-C-E. Самый маленький путь – через С (одна пересадка).В город G рейсовым маршрутом из А попасть нельзя, потому что построенный граф не является связным, а городка А и G соответствуют верхушкам подграфов, любые две верхушки которых Тема 21. Графы, их способы задания (взятые по одной из каждого графа) не являются смежными.

Пример 3.Выстроить граф, для которого задана матрица смежности:

Решение: Изобразим 5 вершин графа точками на плоскости и соединим верхушку с верхушкой линией, если элемент .

КОНТРОЛЬНЫЕ ВОПРОСЫ:

1. Что такое граф?

2. Как определяется степень верхушки?

3. Назовите характеристики степеней вершин.

4. Дайте определение Тема 21. Графы, их способы задания маршруту.

5. Что таковой цикл?

6. Какой граф именуется эйлеровым?

7. Дайте определение дереву.

8. Какими методами можно задать граф?

Домашнее задание: [3], §7.1, 7.2


tema-23-lichnostno-centrirovannaya-psihoterapiya-2-chasa.html
tema-23-mufti-i-tormoznie-ustrojstva.html
tema-23-obshie-polozheniya-ispolnitelnogo-proizvodstva-uchebno-metodicheskij-kompleks-po-podgotovke-specialista-po-napravleniyu.html