Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Непрерывные последовательности ребер графа

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

Маршруты

Пусть граф G(V, Е, f) имеет не более чем счетные множества вершин V={Al,A2,..,Atl} и ребер ?'=^г|,^,..,ая}. Конечная последовательность ребер графа а,,а^,...,а^

(не обязательно различных) называется маршрутом длины к, если граничные точки двух соседних ребер этой последовательности совпадают, т.е. - если существует последовательность ,Ah,A^,...,(не обязательно

различных) вершин, удовлетворяющих условию f(al ) — (Ai & А, ) для любого номера

j = 1,2,...,/:. Вершины До и A/t

называются

соответственно начальной и конечной вершиной маршрута alt ,а^ 9...,a,k. Остальные вершины последовательности

Д , Д , Д ,..., Д называются промежуточными

вершинами этого маршрута. Также говорят, что маршрут al{ ,...,a,t соединяет вершины До и Да . Заметим, что

любое ребро (или петля) является маршрутом длины 1, соединяющим свои граничные вершины. Маршрут называется замкнутым, если его начальная и конечная вершины совпадают. В противном случае маршрут называется незамкнутым.

Пример. На рис. 23 последовательность ребер дрд45622 образует незамкнутый маршрут длины 6, соединяющий вершины А4 и Л2. а последовательность ребер я7, д6457 определяет замкнутый маршрут длины 5, который начинается и р 23

заканчивается в вершине А.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы