АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Понятия смежности, инцидентности, степени

Прочитайте:
  1. II. КОНЦЕПЦИЯ И ВЫРАЖЕНИЕ ПОНЯТИЯ ИГРЫ В ЯЗЫКЕ
  2. III. Критика предложенных в литературе определений понятия изобретения
  3. V. Выпишите рецепты в дневник для лечения больных на ФАПе с диагнозами: «Сальмонеллез средней степени тяжести».
  4. А ТЕРМИНЫ, ПОНЯТИЯ, КОНЦЕПЦИИ
  5. А. Общие понятия о праве.
  6. Алгоритм помощи при преэклампсии легкой степени.
  7. В зависимости от их степени огнестойкости
  8. Введение понятия бисексуальности
  9. Возведение числа a в степень числа b с использованием понятия логарифма.
  10. Все бензодиазепиновые производные в той или иной степени обладают анксиолитическим, седативным, гипнотическим, антиконвульсивным и миорелаксирующим эффектами

Если x ={ v, w } - ребро, то v и w − концы ребра x.

Если x =(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).

Вершины v, w называются смежными, если { v, w }Î X.

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

 

Маршруты и пути

Последовательность v 1 x 1 v 2 x 2 v 3… x k v k+1, (где k ³1, v iÎ V, i =1,…, k +1, x iÎ X, j =1,…, k), в которой чередуются вершины и ребра (дуги) и для каждого j =1,…, k ребро (дуга) x j имеет вид { vj, vj +1} (для ориентированного графа (vj, vj +1)), называется маршрутом, соединяющим вершины v 1 и vk +1 (путем из v 1 в vk +1).

 

Пример

В графе, изображенном на рис.4, v 1 x 1 v 2 x 2 v 3 x 4 v 4 x 3 v 2 – маршрут, v 2 x 2 v 3 x 4 v 4 – подмаршрут;

маршрут можно восстановить и по такой записи x 1 x 2 x 4 x 3;

если кратности ребер (дуг) равны 1, можно записать и так v 1 v 2 v 3 v 4 v 2.

 

Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

 

Дата добавления: 2015-09-27 | Просмотры: 450 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.007 сек.)