работе рассмотрены основные понятия теории графов и её приложения к исследованию линейных систем и задачам минимизации и сетевого планирования. Рассмотрены с подробными объяснениями примеры решения задач различной сложности. Имеются задачи для самостоятельной работы.
Данные методические указания предназначены для самостоятельной работы студентов всех специальностей дневной и заочной форм обучения.
Составители: канд. физ.-мат. наук, доц. ;
ст. преп.
Рецензент: ст. преп.
Ó Санкт-Петербургская государственная академия сервиса и экономики
2004 г.
§1. Основные понятия и определения.. 4
§2. Деревья, остовы, разрезы... 5
§3. Ориентированные графы... 7
§4. Уравнения и графы... 9
§5. Правила упрощения орграфов для систем уравнений.. 11
§6. Построение нормализованного графа.. 16
§7. Задача о кратчайшем пути на графе. Алгоритм Дейкстры... 21
§8. Сетевое планирование.. 25
§9. Задачи для самостоятельной работы... 35
Литература.. 39
Графомназывается совокупность точек, называемых вершинами, и соединяющих их линий, которые называются ребрами. На рис. 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'.
Эйлеровым путем (циклом) графа называется путь (цикл), содержащий все ребра графа ровно один раз. Граф, обладающий эйлеровым циклом, называется эйлеровым графом. Можно доказать, что граф является эйлеровым тогда и только тогда, когда он связен и все его вершины имеют четную степень.
Гамильтоновым путем (циклом) графа называется путь (цикл), проходящий через каждую вершину в точности по одному разу. Граф, обладающий гамильтоновым циклом, называется гамильтоновым. Достаточным условием гамильтоновости является полнота графа.
Деревом называется связный граф, не содержащий циклов. Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Можно показать, что граф Г с n вершинами является деревом тогда
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
