Методические указания к выполнению практической работы

1. Повторите основные понятия, определения и теоремы

2. Выполните № 1, предварительно сделав чертеж и обозначив вершины графа

3. Выполните № 2, построив по таблице граф и (или) дерево

4. Выполните № 3, построив дерево по данному графу

5. Выполните № 4, построив граф

6. В № 5 и № 6 обоснуйте ответ

Графом  называется пара двух конечных множеств: Vножество точек и множество линий, соединяющих некоторые пары точек.

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

Если ребро графа G соединяет две его вершины V и W, т.е. , то говорят, что это ребро им инцидентно.

Две вершины графа называются смежными, если существует инцидентное им ребро.

Два ребра называются смежными, если они имеют общую вершину.

Число рёбер, инцидентных вершине А, называется степенью этой вершины и обозначается        (от англ. degree – степень).

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

Вершина называется чётной (нечётной), если её степень – чётное (нечётное) число.

Теорема 1. Число нечётных вершин любого графа – чётно.

Следствие. Невозможно начертить граф с нечётным числом нечётных вершин.

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

Число рёбер маршрута называется длиной маршрута.

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

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

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

Теорема 2.   Граф G является эйлеровым тогда и только тогда, когда G – связный граф, имеющий все чётные вершины.

Вопросы для самоконтроля:

1. Дайте определение графа и его элементов

2. Дайте определение маршрута и его видов

3. Дайте определение Эйлерова графа и условие его построения