русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Определение 5. Если задана функция и/или , то множество называется множеством меток, а граф (орграф) называется помеченнымиливзвешенным,нагруженным.


Дата добавления: 2013-12-23; просмотров: 552; Нарушение авторских прав


Основные понятия теории графов.

Глава 2. Алгоритмы на графах

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

Графы представляют собой распространенные структуры в математике и информатике, и алгоритмы для работы с графами очень важны. Имеются сотни интересных вычислительных задач, сформулированных с использованием графов.

Определение 1. Неориентированным графом называется совокупность непустого множества – множества вершин и множества - множества ребер, т.е.неупорядоченных пар различных элементов множества .

Число вершин графа обозначается .

Число ребер графа обозначается .

Если - вершины , т. е. и – соединяющее их ребро, то есть , тогда вершина и ребро называются инцидентными. Два ребра, инцидентных одной вершине, называются смежными ребрами. Две вершины, инцидентные одному ребру, называются смежными вершинами.

Количество ребер, инцидентных вершине , называется степенью (валентностью) вершины и обозначается .

Определение 2.Ориентированным графом (орграфом) называется совокупность непустого множества – множества узлов и множества E – множества дуг, т.е. упорядоченных пар различных элементов множества .

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

Граф наглядно изображают диаграммой: вершины – точками, ребро – отрезком . Для орграфа узлы изображают точками, дуга - стрелкой от к .

 

Рис 1. а) граф , б) орграф

Определение 3. Псевдографом (псевдоорграфом) называется совокупность непустого множества и множества неупорядоченных (упорядоченных) пар элементов из необязательно различных.

Ребро (дуга )псевдографа (псевдоорграфа) назывется петлей.



Определение 4. Мультиграфом (мультиорграфом) называется совокупность непустого множества и набора неупорядоченных (упорядоченных) пар элементов из , причем одна и та же пара может входить в набор несколько раз. Такое ребро (дугу) называют кратным ребром (дугой).

 

Рис 2. а) псевдограф, – петля, б) мультиграф, - кратное ребро.

Рис 3. Помеченный орграф. Функция , ,

Далее, по умолчанию, термин «граф », означает неориентированный непомеченный граф без петель и кратных ребер.

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



<== предыдущая лекция | следующая лекция ==>
Скачивание сайтов целиком | Лекция №4. Сечения


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.001 сек.