Всего на сайте:
119 тыс. 927 статей

Главная | Математика

Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»  Просмотрен 149

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

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

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

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

 

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

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

 

Рис. 1.

 

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

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

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

 

Рис.2.

 

Например, кратность ребра {v1, v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3, v4} − трем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предыдущая статья:ЭКСКУРСИОННЫЕ УСЛУГИ Общие требования Следующая статья:Понятия смежности, инцидентности, степени
page speed (0.0077 sec, direct)