Ориентированные графы
Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно. Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее? Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах-улицах рассматриваемой схемы (графа) города.
Граф, на рёбрах которого расставлены стрелки, называется ориентированным.
Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины).
Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину).
рис.14
Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
Ст.вх.А=2, Ст.вых.А=1
Ст.вх.В=2, Ст.вых.В=0
Ст.вх.Д=1, Ст.вых.Д=3
Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер
A1A2, A2A3,..., Аn-1Аn в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.
На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути— простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды. (рис.15)
рис.15
Ориентированным циклом называется замкнутый путь в ориентированном графе.
На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.
|
|
|
рис.16
Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй - 3,
а третий — 4.
Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними.
Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.
рис.17
Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности).
Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞
Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств; при решении многих задач, в частности, комбинаторных.
|
|
|
Тесты к теме
1. Логический элемент «И» выполняет:
А) Логические умножение.
B) Сложение.
С) Деление.
Д) Вычитание.
Е) Сравнение.
2. Законы и методы переработки и накопления информации изучает:
А) информатика.
B) логика
С) кибернетика
Д) статистика
Е) динамика
3. Книга, дискета, жесткие диски служат для:
А) хранение информации.
B) создания информации.
С) передачи информации.
Д) сбора информации.
Е) обработки информации.
4. Информацию, независящую от личного мнения или суждения, можно назвать:
А) достоверной
B) актуальной
С) объективной
Д) полезной
Е) понятной.
5. Какая из операций является отрицанием?
A) NOT.
B) OR.
C) AND.
D) DIV.
E) MOD.
6. Наиболее сложные задачи управления и принятия решений решают:
А) Операционные системы.
B) Системы искусственного интеллекта.
С) Системы бухгалтерского расчета.
Д) Сетевые технологии
Е) Экономические и пакеты
7. Какие функций выполняют операций по вычислению параметров случайных величин или их распределений, представленных множеством чисел?
А) Логические
B) Динамические
С) Статистические
Д) Текстовые
Е) Математические
8.По стадии обработки информация подразделяется на:
А) первичную, вторичную, промежуточную и результатную
|
|
|
B) текстовую и графическую
С) Входную, выходную, внутреннюю и внешнюю.
Д) плановую, нормативно-справочную, учетную и оперативную.
Е) переменную и постоянную.
9. 1 Мбайт информации – это:
А) 1024 Кбайта
B) 1024 байта
С) 1 млн байтов
Д) 1000 Кбайта
Е) 1 млрд бит.
10. Какой раздел информацики разрабатывает общие принципы построения вычислительных систем?
А) Вычислительная техника
B) прграммирование
С) системы проектирования
Д) экспертные системы
Е) искусственный интеллект.
11. Под обменом информацией понимается:
A.Перемещение её из одного накопителя в другой.
B. Её прием или передача.
C.Перевод её на машинный язык.
D.Перемещение из внешней памяти во внутреннюю.
E.Кодирование информации.
Дата добавления: 2016-01-06; просмотров: 26; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!