Краткий перечень основных понятий теории графов.

Министерство образования Российской Федерации

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

Теория графов

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

По подготовке к контрольным работам по дисциплине

«Дискретная математика»

 

Уфа 200 5

Министерство образования Российской Федерации

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра проектирования средств информатики

 

 

ТЕОРИЯ ГРАФОВ

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

 

по подготовке к контрольным работам по дисциплине

«Дискретная математика»

 

Уфа 2005

Составители: Н.И. Житникова, Г.И. Федорова, А.К. Галимов

УДК 519.6 (07)

ББК 22.193 (я7)

 

 

Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика». /Уфимск. гос. авиац. техн. ун-т.; Сост.: Н.И. Житникова, Г.И. Федорова, А.К. Галимов. - Уфа, 2005 -37 с.

 

Предназначены для студентов 1 курса направления 654600: Информатика и вычислительная техника,       : Защита информации для подготовки к контрольным работам по курсу «Дискретная математика».

 

Табл. 2. Ил. 14. Библиогр.: 9 назв.

 

 

Рецензенты:   Газизов Р.К.

                         Васильев В.И.

 

 

© Уфимский государственный

авиационный технический университет, 2005

                                                Содержание

 

Краткий перечень основных понятий теории графов ……………….. 4

Понятия смежности, инцидентности, степени ……………………….. 7

Маршруты и пути ………………………………………………………. 7

Матрицы смежности и инцидентности…..……………………………. 7

Связность. Компоненты связности …………………………………….. 8

Матрицы достижимости и связности ………….………………………. 9

Расстояния в графе …………………………..…………….……………. 9

Образ и прообраз вершины и множества вершин …………..……….. 10

Нагруженные графы ………………..………………………………….. 11

Деревья и циклы …………………………………….………….……… 12

 

Решение контрольных задач по теме «Теория графов»……………………………………………...…………………... 13

Задание 1. Компоненты сильной связности ориентированного графа.……………………………………………………………………. 13

Задание 2. Расстояния в ориентированном графе ..………………...... 16

Задание 3. Минимальный путь в нагруженном ориентированном графе ...……...…………………………………………………………...         20

Задание 4. Эйлеровы циклы и цепи ……..………………………….… 23

Задание 5. Минимальное остовное дерево...………...…………...…… 25

Задание 6. Задача о коммивояжёре...………...…………...…………… 27

 

Задания для самостоятельного решения ………….………......……… 34

 

Список литературы…………………………………………………..…. 37

Краткий перечень основных понятий теории графов.

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

 

Рис. 1.

 

Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения V × V, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V,X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V.

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

 

Рис.2.

 

Например, кратность ребра {v₁,v₂} в графе, изображенном на рис. 2, равна двум, кратность ребра {v₃,v₄} − трем.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

Граф − мультиграф, в котором ни одна пара не встречается более одного раза.

Граф называется ориентированным, если пары (v,w) являются упорядоченными.

Ребра ориентированного графа называются дугами.

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или v_i)– вершина или номер вершины;

G, G₀ - неориентированный граф;

D, D₀ – ориентированный;

{v,w} − ребра неориентированного графа;

{v,v} – обозначение петли;

(v,w) − дуги в ориентированном графе;

v,w - вершины, x,y,z – дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) - количество ребер, m(D) - количество дуг.

 

Примеры

1) Ориентированный граф D=(V, X), V={v₁, v₂, v₃, v₄},

X={x₁=(v₁,v₂), x₂=(v₁,v₂), x₃=(v₂,v₂), x₄=(v₂,v₃)}.

 

Рис. 3.

 

2) Неориентированный граф G=(V, X), V={v₁, v₂, v₃, v₄, v₅},

X={x₁={v₁,v₂}, x₂={v₂,v₃}, x₃={v₂,v₄}, x₄={v₃,v₄}}.

 

Рис. 4.