Теория вероятностей и математическая статистика. Графы

1. Теория вероятностей и математическая статистика. Графы.

Подготовил работу
Студент группы 4996
Малов Константин Васильевич

2. Введение.

В теории вероятностей и математической статистике графы служат мощным
инструментом для моделирования случайных процессов, визуализации
вероятностных связей, формирования сетей событий и систем статистических
зависимостей. Использование графов облегчает изучение сложных структур
данных, помогает выявлять закономерности и разрабатывать методы анализа.

3. Определение графа. Типы графов.

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

4. Способы задания графов.

Перечисление элементов. Исходя из определения, для того, чтобы задать граф,
достаточно перечислить его вершины и ребра (т.е. пары вершин).
Изображение. Если граф не слишком большой, его можно нарисовать. В
неориентированном графе ребра изображают линиями, соединяющими смежные
вершины, в ориентированном – стрелками.
Матрица смежности. Пусть – граф с вершинами, пронумерованными числами от 1
до . Матрица смежности – это таблица с строками и столбцами, в которой
элемент, стоящий на пересечении строки с номером и столбца с номером , равен
1, если вершины с номерами и смежны, и 0, если они не смежны.

5. Способы задания графов.

Матрица инцидентности. Пусть – граф, вершины которого пронумерованы
числами от 1 до , а ребра – числами от 1 до . В матрице инцидентности строки
соответствуют вершинам, а столбцы – ребрам. На пересечении строки с номером
и столбца с номером стоит 1, если вершина с номером инцидентна ребру с
номером , и 0 в противном случае.
Списки смежности. Этот способ часто используется для компьютерного
представления графов. Состоит он в том, что для каждой вершины задается
список всех смежных с ней вершин. В структурах данных, применяемых в
программировании, списки смежности могут быть реализованы как массив
линейных списков. В формулировках задач будем эти списки оформлять так:
пишется номер или имя вершины и после двоеточия перечисляются все смежные
с ней вершины.

6. Операции над графами.

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

7. Помеченные графы.

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

8. Автоморфизм.

Автоморфизм – подстановка на множестве вершин графа, сохраняющая
отношение смежности (две вершины смежны тогда и только тогда, когда смежны
их образы). Иначе говоря, автоморфизм – это изоморфизм графа на себя.
Тождественная подстановка (каждый элемент переходит в себя) является
автоморфизмом любого графа

9. Список использованной литературы.

Боллобаш Б. Теория графов — М.: Наука, 1984.
Харери Ф. Теория графов — М.: Мир, 1973.
Гримметт Д., Стиринг Д. Вероятности и графы — М.: Физматлит, 2007.
Колмогоров А.Н., Фомин С.В. Элементы теории функций и
функционального анализа — М.: Наука, 1976.