Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Понятие ориентированный граф (орграф).






 

Ребро < А, В> называется ориентированным, если одну вершину считают его началом, вторую концом

 
 

 


< А, В>

< В, А>

Граф называется ориентированным, если каждое его ребро ориентировано.

Степенью входа вершины А называется количество ребер входящих в А. Степенью выхода вершины А называется количество ребер выходящих из нее.

 
 

 

 


Рассмотрим

1. вершина А:

степень входа – 1, степень выхода – 1;

2. вершина С:

степень входа – 3, степень выхода – 0;

3. вершина D:

степень входа – 0, степень выхода – 2.

Стоком называется вершина, степень выхода которой равна 0, а степен7ь входа больше 0.

Источником называется вершина, степень выхода которой больше 0, а степень входа равна 0.

Изолированной вершиной называется вершина, у которой степень входа и степень выхода равны 0.

Путем от вершины А1 до вершины Аn называется такая последовательность ребер, ведущих от А1 до Аn < A1, A2> < A2, A3> …< An-1, An>, что конец предыдущего ребра является началом следующего и ни одно ребро не встречается дважды.

Расстоянием от вершины А до вершины В называется длина наименьшего пути. Если пути от вершины А до вершины В не существует, то расстояние считают равным бесконечности.

 

S(A, B)=1

S(A, C)=2

S(C, A)=∞

Теорема: Если в графе m вершин, р – ребер, то степень входа А1+ степень входа А2+…+ степень входа Am = степень выхода А1+ степень выхода А2+…+ степень выхода Am = р

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал