Основы дискретной математики. Основные понятия и определения. Деревья, остовы, разрезы. Ориентированные графы

Страницы работы

42 страницы (Word-файл)

Фрагмент текста работы

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

Данные методические указания предназначены для самостоятельной работы студентов всех специальностей дневной и заочной форм обучения.

Составители: канд. физ.-мат. наук, доц. ;

ст. преп.

Рецензент: ст. преп.

Ó Санкт-Петербургская государственная академия сервиса и экономики

2004 г.


Содержание

§1. Основные понятия и определения.. 4

§2. Деревья, остовы, разрезы... 5

§3. Ориентированные графы... 7

§4. Уравнения и графы... 9

§5. Правила упрощения орграфов для систем уравнений.. 11

§6. Построение нормализованного графа.. 16

§7. Задача о кратчайшем пути на графе. Алгоритм Дейкстры... 21

§8. Сетевое планирование.. 25

§9. Задачи для самостоятельной работы... 35

Литература.. 39


§1. Основные понятия и определения

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

Рис. 1.

Рис. 2.

Ребра, имеющие одинаковые концевые вершины, называются параллельными (e2. e3 на рис.1). Ребро, концевые вершины которого совпадают, называется петлей (e7 на рис.1). Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инцидентные одной и той же вершине, называются смежными ребрами. Например, на рис. 1, вершина v3 и ребро e6 инцидентны друг другу, v1 и v2 – смежные вершины, e5 и e2 – смежные ребра.

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

Маршрутом в графе называется последовательность ребер, ведущая от некоторой начальной вершины vi в конечную вершину vj, в которой каждые два соседних ребра имеют общую вершину. Маршрут называется путем, если все составляющие его ребра различны. Например, в графе, изображенном на рис. 1, последовательность ребер (e1, e4, e3, e2, e6, e7) образует путь, ведущий от вершины v1 к вершине v5. Циклом называется путь, начальная и конечная вершины которого совпадают. На рис. 1 ребра (e1, e4, e2)  образуют цикл. Путь (цикл) называется простым, если он не проходит ни через одну вершину более одного раза. Длиной пути (цикла) называется число содержащихся в нем рёбер.

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

Рассмотрим граф Г=(V,E) с множеством вершин V и множеством ребер E. Граф Г'=(V', E') называется подграфом графа Г, если V' и E' являются подмножествами V и E, причем ребро содержится в E' только в том случае, если его концевые вершины содержатся в V'.

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

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

§2. Деревья, остовы, разрезы

Деревом называется связный граф, не содержащий циклов. Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Можно показать, что граф Г с n вершинами является деревом тогда

Похожие материалы

Информация о работе

Тип:
Методические указания и пособия
Размер файла:
1 Mb
Скачали:
0