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

4862
0
08 июля 2009
(38.1.) Одним из базовых разделов дискретной математики можно назвать теорию графов. Их применяют при решении задач теории автоматического управления. Применение их актуально и в таких науках, где существуют системы с большим количеством объектов, которые предполагают взаимосвязь, определяемую разнообразными отношениями.
Примером могут быть большие молекулы, системы трубопроводов, технологические линии, сети железных дорог, системы заводов-потребителей и предприятий-поставщиков и др.

 

О: Под графом понимают упорядоченную пару конечных множеств38.1_html_m11de5e45.gif, в котором38.1_html_m31b9de3a.gifпредставляет собой множество точек, именуемых вершинами графа,38.1_html_71fe7080.gifесть множество пар элементов из38.1_html_m2756962b.gif, которые носят название ребер графа. Ребро38.1_html_3941669d.gifслужит соединением вершин38.1_html_m4a8a5a88.gifили является инцидентным данным вершинам. Вершины38.1_html_m4a8a5a88.gifсмежные или инцидентные ребру38.1_html_m711df4fc.gifДва ребра можно определить в качестве смежных при условии, что они инцидентны одной вершине. Граф с38.1_html_6efbf575.gifвершинами и38.1_html_mba85680.gifребрами имеет название38.1_html_75b15911.gif-графа. Ориентированным граф (орграф)38.1_html_43586c52.gifявляется тогда, когда38.1_html_666415cc.gif- множество упорядоченных пар из38.1_html_m145c1767.gif, иными словами, если его ребра направлены, такие направленные ребра именуют дугами.

Для каждого графа соответствует некоторая схема на плоскости при обозначении вершин в качестве точек, а ребер — линий. Такая схема носит название диаграммы графа, ее также называют просто графом. Ребра на диаграмме могут быть представлены в качестве отрезков прямых или дуг линий. Один и тот же граф можно обозначить разными диаграммами. Так, на рис. 38.1, 38.2 показан один и тот же неориентированный граф38.1_html_73595f5e.gif, в котором38.1_html_44d12d9d_show.gifЭти диаграммы имеют название изоморфных.

 38.1_html_m12b9b72f.gif
Рис. 38. 1

38.1_html_3595302.gif
38.1_html_5552f961.gif
Рис. 38. 2

38.1_html_43cfd67c.gif
 

Рис. 38. 3

 

 

На рис. 38.3. обозначен ориентированный граф38.1_html_m559c9cf8.gif

38.1_html_6b028247_show.gifДля данного графа характерно наличие петли, т.е. существует ребро, которое соединяет вершину с ней самой, и кратных ребер, когда две вершины соединены несколькими ребрами.

О: Граф, у которого есть кратные ребра, носит название мультиграфа, граф, не имеющий кратных ребер, называется простым графом.

О: Степень вершины38.1_html_43586c52.gifесть количество ребер, которые являются инцидентными38.1_html_m45e2bcf6.gif.

Так, для графа, обозначенного на рис. 38.3, степень вершины38.1_html_m45e2bcf6.gifравна 2, вершины38.1_html_55ea5b6.gif- 5. Определяют граф также посредством некоторой матрицы.

О: Под смежностью графа38.1_html_3f7dbcc9.gifподразумевают квадратную матрицу38.1_html_149b743d.gif38.1_html_m7f54c688.gif-го порядка, ее столбцам и строкам соответствуют вершины графа. Для неориентированного графа число38.1_html_m1cd85b44.gifэквивалентно количеству ребер, инцидентных38.1_html_m1cd85b44.gifравно количеству ребер с началом38.1_html_m60b4585f.gifи концом38.1_html_5157ddba.gif

Обозначим матрицы смежности графов на рис. 38.1 и 38.3 соответственно:

 

38.1_html_1b1e7b88.gif

 

Отметим, что матрица смежности неориентированного графа симметрична:38.1_html_536fa07b.gif, к тому же сумма чисел в любой ее строке или столбце совпадает со степенью соответствующей вершины.

Возможным представляется построение диаграммы графа по матрице смежности.

Таким образом, граф определяется матрицей смежности, диаграммой или списком ребер.



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
2463 0
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
7208 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
8987 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    Радиомастер
    © 2005–2013 radiomaster.ru
    admin@radiomaster.ru
    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.7345 s