Теория графов
ОТЧЕТ ПО ДИСЦИПЛИНЕ «ОСНОВЫБИБЛИОГРАФИИ»
студента 1 курса 132 группы
специальности 090301 «Компьютерная безопасность»
факультета компьютерных наук и информационных технологий
Донских Дениса Сергеевича
Преподаватель
Доцент А. В. Жаркова
Саратов 2012
Содержание
Введение 3
1.Основные определения теории графов 4
2.Основные теоремы теории графов 6
Заключение 8
Список использованных источников 9
Введение
Высокие темпы информатизации различных видов деятельности в настоящее время привели к тому, что появилась возможность компьютерного моделирования и проектирования сложных систем, изучения их свойств и управления ими в условиях дефицита времени, ограниченности ресурсов, неполноты информации. Однако для исследования характеристик любой системы математическими методами должна быть обязательно выполнена формализация, то есть построена математическая модель. Исследования с помощью математических моделей зачастую являются единственно возможным способом изучения сложных систем и решения важнейших практических задач управления.
Графы оказались хорошей математической моделью широкого класса объектов и процессов. Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электроника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. При этом обычно на графе решаются задачи о достижимости, задачи сетевого планирования, потоковая задача.[1]
Общие понятия теории графов
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783).
Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).
Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.[2]
Построим последовательности вершин графа (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.
Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 1 изображен связный граф.
Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.
Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.[1]
Основные теоремы теории графов
Теория графов, как было сказано выше, – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.
Определение: Графомназывается совокупность конечного числа точек, называемыхвершинамиграфа, и попарно соединяющих некоторые из этих вершин линий, называемыхребрамиилидугамиграфа.
Определение: Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.
Определение: Граф, состоящий только из изолированных вершин, называется нуль - графом. Обозначение: O '– граф с вершинами, не имеющий ребер
Определение: Граф, в котором каждая пара вершин соединена ребром, называется полным. Обозначение: U' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали.
Определение: Степеньювершиныназывается число ребер, которым принадлежит вершина. Обозначение: p(A) – степень вершины A.
Определение: Граф, степени всех k вершин которого одинаковы, называется однороднымграфомстепени k.
Определение: Дополнениемданногографаназывается граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.
Определение: Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.
Определение: Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.[3]
Определение: Путемот A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.
Определение: Цикломназывается путь, в котором совпадают начальная и конечная точка.
Определение: Простым цикломназывается цикл, не проходящий ни через одну из вершин графа более одного раза.
Определение: Длиной пути, проложенного на цикле, называется число ребер этого пути.
Определение: Две вершины A и B в графе называются связными(несвязными), если в нем существует (не существует) путь, ведущий из A в B.
Определение: Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.
Определение: Деревомназывается связный граф, не содержащий циклов.
Определение: Несвязный граф, состоящий исключительно из деревьев, называется лесом.
Определение: Дерево, все n вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами.[4]
Заключение
Итак, мы рассмотрели что такое граф, как он определяется и применяется на практике. Так же в данной работе были рассмотрены основные определения теории графов, без которых было бы невозможно доказательство теорем, а, следовательно и решение задач.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Соросовский, В.А. Теория графов. Изд-во Россия, 2001. 101с.2. Гарднер, М.Г. Исследование графов / М.Г. Гарднер // Журн. структур. графов. 1997. Т. 13, № 8. С. 14-19.3. Теория графов [Электронный ресурс] // Википедия [Электронный ресурс]: свободная энциклопедия / текст доступен по лицензии Creative Commons Attribution-ShareAlike; Wikimedia Foundation, Inc, некоммерческой организации. Электрон. дан. (938214 статей, 3196502 страниц, 141243 загруженных файлов). Wikipedia®, 2001-2012. URL: https://ru.wikipedia.org/wiki/Теория графов (дата обращения: 10.12.2012). Загл. с экрана. Последнее изменение страницы: 13:04, 9 ноября 2012. Яз. Рус.4. Зыков А. А. // Энциклопедия графов: в 2 т. / глав. ред С.Н. Олехин. 2-е изд. М., 1975. Т. 19: Графы. С. 189. Сведения доступны также по Интернет: https://insiklopedi-grafov.com/0246/46454.html (дата обращения: 20.11.2012). Яз. рус.