Теория графов. Основные понятия теории графов. Операции над графами. Способы задания графов. Плоские графы, маршруты, цепи, циклы графа.

Вопросы, рассмотренные в данной лекции

1. Основные понятия теории графов (определение графа, его изображение, элементы графа, ориентированные и неориентированные графы, подграф, симметричный граф...)

2. Рассмотрены примеры приложений теории графов.

3. Степень вершины графа

4. Маршруты, цепи, циклы графа

5. Все об ориентированных графах

6. Изоморфизм графов

7. Плоские графы

8. Операции над графами

9. Способы задания графов

10. Эйлеровы графы

11. Гамильтоновы графы

Лекция по дискретной математике

Графические представления в широком смысле – любые наглядные отображения исследуемой системы, процесса,  явления на плоскости. К ним могут быть отнесены рисунки, чертежи, графики зависимостей характеристик, планы-карты местности, блок-схемы процессов, диаграммы и т. д. Такие изображения наглядно представляют различные взаимосвязи, взаимообусловленности: топологическое (пространственное) расположение объектов, хронологические (временные) зависимости процессов и явлений, логические, структурные, причинно-следственные и другие взаимосвязи.

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

Всё более распространенными становятся представления количественных характеристик, взаимосвязей между объектами в виде разного рода одно-, двух- и более мерных гистограмм, круговых диаграмм, других аналогичных способов представления в виде тех или иных геометрических фигур, по наглядным характеристикам которых (высоте, ширине, площади, радиусу и пр.) можно судить о количественных соотношениях сравниваемых объектов, значительно упрощая их анализ.

Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы, изучаемые в теории графов.

Теория графов – это раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы.

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

Граф – это система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа – см. рисунок 1). Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами.

Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.

Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и тогда определение графа таково:

Скачать Теория графов. Лекция по теме графы, операции над графами...

Рекомендуем посмотреть:

Теория графов. Деревья. Сети. Сетевые модели представления информации. Применение графов и сетей