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

Прочие связанные определения

Прочитайте:
  1. IV. Анализ предложенного определения
  2. VIII. Прочие
  3. Анемии, связанные с нарушением синтеза гема
  4. Анемии, связанные с нарушением синтеза глобина
  5. Б. стоимость основных фондов в ценах, учитывающихся при их постановке на баланс, с учетом износа на дату определения
  6. Болезни, связанные с нарушением числа половых хромосом
  7. Болезни, связанные с числовыми аномалиями половых хромосом
  8. В. Для определения объема поражения при переднем инфаркте миокарда.
  9. Вопросов для определения когнитивного стиля
  10. Вредные стороны совокупления, связанные с этим состоянием, и злокачественность некоторых его способов

Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Ориентированным путём в орграфе называют конечную последовательность вершин , для которой все пары являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины и являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

  • Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
  • Всякий простой неэлементарный путь содержит элементарный цикл.
  • Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
  • Петля — элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

Ребро графа называется мостом, если его удаление увеличивает число компонент.


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







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