|
Графназывается ориентированный, если он состоит упорядоченных пар вершин (кортежи длины 2). Такой граф называется также направленным графом или орграфом.
В направленном графе ребра изображаются стрелками, идущими от первой компоненты (начало ребра) кортежа ко второй (конец ребра). См рисунок.
Ребра ориентированного графа имеют определенные фиксированные начало и конец и часто называются дугами.
Дуги орграфа называются кратными, если они имеют одинаковые начальные и конечные вершины, т.е. одинаковые направления. (соединят одну и туже пару вершин). При этом граф имеет несколько разных дуг, соединяющих одну и туже пару вершин.
Рассмотрим неориентированный граф, состоящий их n вершин. Если от некоторой вершины можно пройти к другой вершине по ребрам графа, то получим маршрут перехода. При этом для одних и тех же вершин может оказаться несколько маршрутом. При решении конкретной задачи в таких случаях приходится выбирать наиболее оптимальный маршрут.
Маршрутом называется последовательность попарно инцидентных вершин V1,V2, …, Vi неориентированного графа, т.е. последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего.
Длиноймаршрута называется число ребер этого маршрута.
Маршрут принято задавать как последовательность ребер, поскольку это более удобно при наличии кратных ребер.
Маршрут называется замкнутым или циклом, если начальная вершина маршрута совпадает с конечной,
Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой маршрут. Расстояние обозначается символами d( A;B)= min|A;B|=k, где вершины A и B начало и конец маршрута, k – число, равное наименьшей длине маршрута.
Поскольку рассматриваются конечные графы, минимум можно найти всегда. Формально можно ввести расстояние d(VV) = О, между любой вершиной и ей же самой, что соответствует нулевому маршруту, у которого начало и конец в одной вершине.
В маршруте одно и то же ребро может встретиться несколько раз.
Если ребро встретилось только один раз, то маршрут называется цепью. Запись вида 3-цепь означает, что между двумя точками имеется цепь – маршрут, длина которого равна 3.
В орграфе маршрут является ориентированным и называется путем. На путь сразу налагаются важные требования, являющиеся частью определения:
• направление каждой дуги должно совпадать с направлением пути;
• ни одно ребро пути не должно встречаться дважды.
Поэтому путь - упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.
В графе цепь, путь и цикл называются простыми, если они проходят через любую из вершин не более одного раза.
Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут.В противном случае он называется — несвязным.
Дата добавления: 2015-11-04; просмотров: 19 | Нарушение авторских прав
<== предыдущая лекция | | | следующая лекция ==> |
Мастер курса Заслуженный Артист Р.Ф. Е.Р.Ганелин. | | | - Вот же ж, гад крылатый, мне и так дышать трудно, а он такое вытворяет! - Отдышавшись, после полета, и не в силах подняться с земли, она налетела на Серафима. - Угробить меня решил? И это твоя |