ДМ_Конспект
.pdfЦепь (Chain, trail)
1.В неориентированном графе маршрут, все ребра которого различны.
2.В ориентированном графе последовательность вершин v , ..., v, в которой соседние вершины v и v определяют дугу (либо (v , v), либо (v, v)). Цикл (Loop, Circuit, Cycle) – цепь, концы которой совпадают.
Циклический граф (Cyclic graph)
связный регулярный степени 2 граф, т.е. граф, единственная компонента связности которого есть простой цикл.
Эйлеров граф (Eulerian graph)
связный граф, в котором есть эйлеров цикл; для того чтобы граф был эйлеровым необходимо и достаточно четности степеней вершин. Э.г. можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.
Эйлеров контур (Eulerian cycle, eulerian trail)
контур, проходящий по каждой дуге орграфа в точности один раз.
Эйлеров орграф (Eulerian digraph)
орграф, в котором есть эйлеров контур; для того чтобы орграф был эйлеровым необходимо и достаточно, чтобы в каждой вершине полустепень захода равнялась полустепени исхода.
Эйлеров цикл (Eulerian circuit)
цикл, проходящий через все ребра графа в точности один раз.
Эйлерова цепь (Eulerian chain)
цепь, проходящая через каждое ребро в точности один раз; для существования Э.ц. необходимо и достаточно, чтобы в графе было ровно две вершины с нечетными степенями.
Эксцентриситет вершины (Eccentricity of a vertex)
для данной вершины u величина
где d(u,v) – расстояние между вершинами u и v. Наибольший из Э. вершин есть диаметр графа, наименьший – радиус.
291
Электронное учебное издание
КОНСПЕКТ ЛЕКЦИЙ по дисциплине
«ДИСКРЕТНАЯ МАТЕМАТИКА»
для студентов всех форм обучения направления 6.050101 – «Компьютерные науки»
Составители |
ВАСИЛЬЦОВА Наталия Владимировна |
ЧАЛАЯ Лариса Эрнестовна
Авторская редакция
292