Теория:
Наглядным средством представления состава и структуры системы является граф.
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними — отрезками или дугами.
Основы теории графов как математической науки заложил в \(1736\) г. Леонард Эйлер, рассматривая задачу о Кёнигсбергских мостах. Сегодня эта задача стала классической.
Графом называется конечное множество точек, некоторые из которых соединены линиями.
Обрати внимание!
Точки называются вершинами графа, а соединяющие линии — рёбрами.
Количество рёбер, выходящих из вершины графа, называется степенью вершины.
Обрати внимание!
Вершина графа, имеющая нечётную степень, называется нечётной, а чётную степень — чётной.
Изолированная вершина — вершина, степень которой равна \(0\).
Конечная вершина графа — вершина, степень которой равна \(1\).
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй.
Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двусторонним, поэтому вершины соединены линиями без стрелок.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Граф, в котором все вершины соединены рёбрами, называется неориентированным.
Цепь — путь по вершинам и рёбрам, включающий любое ребро графа не более одного раза.
Цикл — цепь, начальная и конечная вершины которой совпадают.
Граф с циклом называют сетью.
Ориентированный граф — граф, рёбрам которого присвоено направление.
С помощью таких графов могут быть представлены схемы односторонних отношений.
Если все вершины графа чётные, то можно одним росчерком пера начертить граф. При этом начать движение можно с любой вершины и закончить в той же вершине.
Граф с двумя нечётными вершинами также можно начертить одним росчерком. Начинать движение надо с одной нечётной вершины, а заканчивать в другой.
Граф с большим количеством нечётных вершин невозможно начертить таким образом.
Источники:
Изображения ©ЯКласс