Файл: Городского округа г. Выкса Нижегородской области Графы в математике Физикоматематическое отделение Секция математическая.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 51
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
В обыкновенном графе две вершины могут соединяться только одним ребром. Если они соединены более чем одним ребром, то такой граф называется мультиграфом. Если вершина мультиграфа может соединяться сама собой, то такой граф называется псевдографом. Ребро, начало и конец которого находятся в одной вершине, называется петлей.
Применительно к различным вариантам обхода графа используются следующие обозначения. Пусть G – помеченный граф с вершинами V0, V1, V2, … и ребрами Х1, Х2, Х3, …Тогда маршрутом в графе G будет называться конечная последовательность вида V0, Х1,V1,… ,Vn-1, Xn, Vn, в которой чередуются ребра и вершины. Запись вида (V0, V1, …Vn) подразумевает, что любые две вершины соединяются только одним ребром, и маршрут определяется указанной последовательностью вершин. Если V0=Vn, то есть исходная и конечная вершина маршрута совпадают, то маршрут является замкнутым, иначе – открытым. Путь – это маршрут, в котором каждое ребро проходит только один раз. Замкнутый маршрут, содержащий n разных вершин, называется циклом. Любой цикл можно представить графически в виде многоугольника.
Если между любыми двумя вершинами графа можно провести маршрут, то говорят, что граф является связным. Для связных графов имеет смысл определить расстояние между вершинами u и v как минимальное количество рёбер, образующих маршрут между u и v.
В приведенных ниже двух примерах на рисунке 7 слева изображен связный граф, на рисунке справа - несвязный.
В 
А
DC
E Рис.7
2.4. Виды графов
2.4.1.Геометрические и полные графы
Циклы – это очень простые маршруты, проходящие через все вершины, начальная и конечная точка которых совпадают. Примеры циклов представлены на рисунке 8а,б. 
Рис.8,а Рис.8,б
Подобными графами можно представить маршруты городских автобусов или маршруты патрулей. Число вершин V равно числу рёбер А.
Совокупность циклов образует так называемый геометрический граф – плоскую фигуру из вершин (точек плоскости) и рёбер (линий, соединяющих некоторые пары вершин). Область, ограниченная рёбрами и не содержащая внутри себя вершин и рёбер графа, называется гранью. Подсчитать общее число вершин V и число рёбер А несложно.
При подсчете числа граней
С следует учитывать, что внешняя часть плоскости также образует грань, так как она тоже ограничена циклом из вершин и ребер графа. Таким образом, граф, изображенный на рисунке 9, имеет 10 вершин, 14 ребер и 6 граней.
Рис.9Графы, в которых любая пара вершин соединена ребром, называются полными. На следующих рисунках 10а,б,в,г,д,е приведены полные графы с числом вершин от 2 до 7. Полный граф с n вершинами обозначается Кn.
К2
К3 К4
а) б) в)
