Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Понятие цепи




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

и - концевые вершины цепи.

Длина цепи - число ребер, образующих цепь ( и - концевые вершины цепи).

Цепь называется составной, если она содержит повторяющиеся ребра. Цепь называется сложной, если она содержит повторяющиеся вершины за исключением, быть может, первой и последней. Цепь, которая не является ни составной, ни сложной называется простой. Цепь называется циклом, если концевые вершины цепи совпадают. Циклы также бывают простые, составные и сложные. - простой цикл, состоящий из ребер. Пусть и - некоторые вершины графа. Тогда расстояние между вершинами . Введенное таким образом понятие расстояния является метрикой на графах:

1) ;
2) ;
3) .

Диаметром графа называется величина .

Пример

(целая часть числа).


Поделиться:

Дата добавления: 2015-02-10; просмотров: 129; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты