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

Граф называется ориентированный, если он состоит упорядоченных пар вершин (кортежи длины 2). Такой граф называется также направленнымграфом илиорграфом.



Графназывается ориентированный, если он состоит упорядоченных пар вершин (кортежи длины 2). Такой граф называется также направленным графом или орграфом.

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

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

Дуги орграфа называются кратными, если они имеют одинако­вые начальные и конечные вершины, т.е. одинаковые направле­ния. (соединят одну и туже пару вершин). При этом граф имеет несколько разных дуг, соединяющих одну и туже пару вершин.

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

Маршрутом называется последовательность попарно инцидентных вершин V1,V2, …, Vi неориентированного графа, т.е. последовательность ребер не­ориентированного графа, в которой вторая вершина предыдуще­го ребра совпадает с первой вершиной следующего.

Длиноймаршрута называется число ребер этого маршрута.

Маршрут принято задавать как последователь­ность ребер, поскольку это более удобно при наличии кратных ребер.

Маршрут называется замкнутым или циклом, если начальная вершина маршрута совпадает с конечной,

Расстоянием между двумя вершинами называется минималь­ная длина из всех возможных маршрутов между этими вершина­ми при условии, что существует хотя бы один такой маршрут. Расстояние обозначается символами d( A;B)= min|A;B|=k, где вершины A и B начало и конец маршрута, k – число, равное наименьшей длине маршрута.

Поскольку рассматриваются конечные графы, минимум мож­но найти всегда. Формально можно ввести расстояние d(VV) = О, между любой вершиной и ей же самой, что соответствует нулевому маршруту, у которого начало и конец в одной вершине.

В маршруте одно и то же ребро может встретиться несколько раз.

Если ребро встретилось только один раз, то маршрут называ­ется цепью. Запись вида 3-цепь означает, что между двумя точками имеется цепь – маршрут, длина которого равна 3.

В орграфе маршрут является ориентированным и называется путем. На путь сразу налагаются важные требования, являющиеся частью определения:



• направление каждой дуги должно совпадать с направлением пути;

• ни одно ребро пути не должно встречаться дважды.

Поэтому путь - упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.

В графе цепь, путь и цикл называются простыми, если они проходят через любую из вершин не более одного раза.

Неориен­тированный граф называется связным, если между любыми дву­мя его вершинами есть маршрут.В противном случае он называется — несвязным.

 


Дата добавления: 2015-11-04; просмотров: 19 | Нарушение авторских прав




<== предыдущая лекция | следующая лекция ==>
Мастер курса Заслуженный Артист Р.Ф. Е.Р.Ганелин. | - Вот же ж, гад крылатый, мне и так дышать трудно, а он такое вытворяет! - Отдышавшись, после полета, и не в силах подняться с земли, она налетела на Серафима. - Угробить меня решил? И это твоя

mybiblioteka.su - 2015-2024 год. (0.006 сек.)