Автор: Пользователь скрыл имя, 22 Октября 2012 в 23:17, реферат
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.
Теория графов является частью как
топологии, так и комбинаторики.
То, что это топологическая теория,
следует из независимости свойств
графа от расположения вершин и вида
соединяющих их линий. А удобство
формулировок комбинаторных задач
в терминах графов привела к тому,
что теория графов стала одним
из мощнейших аппаратов
Теория графов — раздел дискретной математики, изучающий свойства графов. Теория графов имеет широкие практические приложения. Многие проблемы, возникающие в таких весьма различных областях знания, как психология, химия, электротехника, планирование перевозок, управление, торговля и образование, могут быть сформулированы как задачи теории графов. Ввиду этого теория графов интересна не только сама по себе, но также и тем, что представляет общую основу, на которой результаты, полученные в различных областях знания, могут быть собраны, классифицированы, обобщены и распространены.[1]
Как прикладная дисциплина теория графов
позволяет описывать и
Рис. 1.
Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения VЧV, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V,X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V. [4]
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
Рис.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) - количество дуг.
Примеры
1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},
X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.
Рис. 3.
2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},
X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.
Рис. 4.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра.
Теория графов, как было сказано выше, – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории. [3]
Определение. Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек .
В дальнейшем вершины графа мы будем обозначать латинскими буквами A, B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.
Определение. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.
Определение. Граф, состоящий только из изолированных вершин, называется нуль-графом.
Обозначение: O' – граф с вершинами, не имеющий ребер
Определение. Граф, в котором каждая пара вершин соединена ребром, называется полным.
Обозначение: U' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали
Определение. Степенью вершины называется число ребер, которым принадлежит вершина.
Обозначение: p (A) – степень вершины A.
Определение. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k.
Определение. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.
Определение. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.
Однако,
заметим, что не каждый граф
является плоским, хотя
Определение. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.
Понятия плоского
графа и грани графа
Определение. Путем от A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.
Определение. Циклом называется путь, в котором совпадают начальная и конечная точка.
Определение. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.
Определение . Длиной пути, проложенного на цикле, называется число ребер этого пути.
Определение. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.
Определение. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.
Определение. Деревом называется связный граф, не содержащий циклов.
Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли
Определение. Несвязный граф, состоящий исключительно из деревьев, называется лесом.
Определение 2.13. Дерево, все n вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами.
Заключение.
Итак, мы рассмотрели основные определения теории графов, без которых было бы невозможно доказательство теорем, а, следовательно и решение задач. Однако теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
Список использованных источников