Геометрический (графический) 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Геометрический (графический)



Геометрический (графический)

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

Теоретико-множественный


Матричный

а) Матрица инцидентности

n-число вершин, m – число дуг или ребер

Для неорграфа:

б) Матрица смежности

Неорграф:

Орграф:

Маршруты, цепи, циклы

Маршрутом в графе называется {x1,r1,x2,r2,…xn}

чередующиеся последовательность вершин и ребер/дуг.

Неорграф:

Цепью ρ=(r1, … rn) называется упорядоченная последовательность ребер в которой у каждого ребра ri одна из граничных вершин является граничной вершиной ri-1, а другие ri+1. Если вершины и ребра в цепи различны, то маршрут называют простой цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь называется простым циклом.

Орграф:

Путем в графе называется упорядоченная последовательность дуг μ = (U1, …, Un), в которой конец предыдущей дуги совпадает с началом последующей. Путь у которого начальные и конечные вершины совпадают – контур. Длина цепи – число ребер в цепи. Граф называется связным, если любая пара его вершин соединены цепью. Минимальная длина цепи, соединяющая вершины xi и xj называется расстоянием. Максимальное расстояние между вершинами графа называется диаметром графа. . Цепь (неорграф) называют составной, если в ней повторяется хотя бы одно ребро; сложной, если повторяется хотя бы одна вершина. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа ровно 1 раз. В орграфе путь, проходящий через все вершины ровно 1 раз, называется гамильтоновым, если у него начальная и конечная вершина совпадают, то гамильтонов контур.

 

 

Алгоритм Дейкстры.

Пусть l (xi) – пометка вершины xi.

Шаг 1. Присвоение начальных значений. Положить l* (s) = 0 и считать эту пометку постоянной. Положить l (xi) = ∞ (бесконечность) для всех xi ¹ s и считать эти пометки временными. Положить р=s.

Шаг 2. Обновление пометок. Для всех вершин xi Î Г (р), имеющих временные пометки, изменить пометки в соответствии с выражением:

l (xi) = min{ l (xi), l (p) + c (p, xi)}. (2.3)

Шаг 3. Превращение пометки в постоянную. Среди всех вершин с временными пометками найти такую, для которой l* (xi) = min{ l (xi)}.

Шаг 4. Считать пометку вершины xi* постоянной и положить p = xi*.

Шаг 5. Если р=t, то l* (р) является длиной кратчайшего пути. Конец.
Если р ¹ t, перейти к шагу 2.

Как только длина кратчайшего пути от s до t будет найдена [она будет постоянной пометкой вершины l* (t)], сами пути можно получить с помощью рекурсивной процедуры. Так, для вершины xk, непосредственно предшествующей вершине t в кратчайшем пути от s к t, будет соблюдаться отношение: l* (xk) + c (xk, t) = l* (t).

Таким образом, для любой вершины xi можно найти предшествующую вершину xk, принадлежащую пути m (s, t), для которой справедливо:

l* (xk) + c (xk, xi) = l* (xi). (2.4)

Если существуют несколько кратчайших путей от s к t, то данное соотношение будет выполняться для нескольких вершин. В этом случае выбор пути может быть произвольным.

 

Распределительный метод.

1) Поиск исходного решения

Первоначальное решение ищут методом северо-западного угла. Запись таблицы идет последовательно с левой верхней в правую нижнюю

А1B1->АnBn

2) Проанализируем пустые(=0) клетки

Исследуем перспективность клетки А1В3 полагая, что Х13=1.Для оценки переспективности пустой клетки строится прямоугольник принятия решиений, в котором все углы кроме исследуемого должны быть заняты т.у в них величины Хij<>0

После анализа всех пустых клеток выбирается клетка с максимальным значением потенциала «-», если клеток с «-» значением нет, то полученно оптимальное решение

3) Перераспределение полученного решения

Перераспределение производится в пределах многоугольника принятия решений для переспективных клеток.

В клетках с «-» индексом из значений переменных вычитается минимальное значения переменной, стоящих в этих клетках и это же значение прибавляется к значению переменных, стоящих в клетках с «+» индексами.
В оставшихся клетках значения переменных остаются прежними.

После перераспределения делается очередная итерация заключающаяся в поиске перспективной клетки и очередном перераспределении.

Цикломатическое число графа

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

Цикломатическая матрица:

Цикломатическим числом графа ν(G) – называется число базисных циклов, через которые можно выразить любой другой цикл.

ν(G)=m-n+1, где m – сигнатура; n – множество вершин.

Для приведенного выше графа ν(G)=5-4+1=2, т.е. имеется 2 независимых цикла и что можно убрать 2 ребра так, чтобы получился связанный граф без циклов.

Теорема Эйлера: число элементов базисной системы циклов графа постоянно и равно его цикломатическому числу.

 

(11) Деревья. Остовное дерево минимального веса Дерево - это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность - отсутствие циклов и то, что между парами вершин имеется только по одному пути. Ориентированное (направленное) дерево - ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями Теорема. В связном графе (M, N, T) найдется частичный связный граф (M, N, T) В котором |M| - 1= |N'| = k и можно перенумеровать вершины из M числами от О до k, a дуги из N' числами от l до k таким образом, что для любой дуги u? N' выполн. Задача о кратчайшем остовном дереве. Пусть каждой дуге J графа (M, N, T) сопоставлено неотрицательное число l[j] именуемое длиной этой дуги Требуется построить такое остовное дерево (M, N, T) У которого сумма Длин дуг была бы минимальна.

 

 

(12) Топологическая сортировка графа. Алгоритм Демукрона Топологическая сортировка - один из основных алгоритмов на графах, который примен. для реш. множества более сложных задач. Задача тополог. сортировки графа сост. в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует. Ориентир. сетью назыв. бесконтурный ориентир. граф. В задачах подобного плана рассматриваются только конечные сети. Алгоритм Демукрона — алгоритм решения задачи тополог. сортировки, то есть упорядочения вершин графа по их уровням для бесконтурного ориентир. графа. Уровни вершин графа можно рассматривать как длины max путей от входов до этих вершин. Основная идея алгоритма Демукрона состоит в послед. удалении из сети, начиная со входов, вершин и исходящих из них дуг. Алгоритм исп. матрицу смежности вершин В типа n x n в качестве средства представления сети и основан непосредственно на определении уровня вершины и свойствах матрицы В.

 

 

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

1) Дополнение графа G = (x, U).

Это граф , у которого носитель совпадает с исходным графом и множество дуг есть дополнение для множества дуг U.

2) Объединение графов

При условии, что не пересекаются

G = (x, U) у которого множество вершин объединены с и дуги образованы с .

3) Сумма графов

Граф G = (x, U) образован путем объединения графов и построения полного двудольного графа, у которого одна доля представляет собой множество , а 2 доля

4) Удаление вершины x из графа G = (x, U)

5) Удаление ребра из графа

 

 

Продолжение.

Толщиной графа G называется наименьшее число планарных графов, в результате объединения которых получается исходный граф G. Толщина планарного графа равна 1.

Нижняя оценка толщины t (G) определяется неравенством

, (9.3)

где – большее целое число, | X | = n, Si – степень i -й вершины.

Планарные и плоские графы.

Граф G=(X, U) называется плоским, если его ребра, расположенные на плоскости, могут иметь общие точки только в инцидентных им вершинах, т.е. не пересекаются (рис. 9.1).

Граф, изоморфный плоскому и расположенный на плоскости с пересечением ребер, называется планарным (рис. 9.2).

Область плоскости, ограниченная ребрами плоского графа, внутри которой нет ни вершин, ни ребер, называют гранью. Ребра грани образуют простой цикл. Заметим, что плоский граф имеет всегда одну бесконечную грань, не ограниченную ребрами (f6 на рис. 9.1).

Существует формула Эйлера, позволяющая установить связь между числом вершин n, ребер m и граней f плоского графа:

n – m + f = 2.

Теорема Понтрягина – Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному графу K5 и полному двудольному графу K3,3 (рис. 9.3,а,б).

Основываясь на критерии Понтрягина, можно получить еще один критерий планарности, введя понятие элементарного стягивания, состоящего в следующем. При стягивании любого ребра графа оно исключается, а обе вершины a и b, инцидентные ему, отождествляются (рис. 9.3,а,б). Полученная при этом вершина инцидентна тем же ребрам, что и a, b (кроме исключенного ребра).

Теорема Харари. Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых к K5 и K3,3.

Теорема Харари является двойственной формой теоремы Понтрягина-Куратовского.

Минимальное число ребер, которое нужно удалить из графа, чтобы он стал планарным, называется числом планарности и обозначается Q(G).

Для полного графа Kn c n ³ 4 вершин Q(G) определяется как

.

 

Эйлеров путь в графе.

Маршрут (u1, u2,..., uq) называется циклом, если в нем начальная вершина дуги u1 совпадает с конечной вершиной дуги uq.

Так, например, в графе, приведенном на рис. 3.1, последовательности дуг:

m1 ={ u1, u5, u2 }, m2 ={ u1, u5, u2, u3, u10, u4 }, m3 ={ u1, u5, u8, u10, u4 },

m4 ={ u1, u5, u8, u10, u4, u2, u9, u7, u6, u3 } – являются циклами.

Цикл называется эйлеровым, если он содержит все ребра графа ровно один раз.

Теорема (Эйлера). Граф содержит эйлеров цикл только тогда, когда все его вершины имеют четную степень.

Например, граф, изображенный на рис. 3.1, будет содержать Эйлеров цикл (m4), а граф, изображенный на рис. 3.2, – нет.

Цикл называется простым, если каждая вершина, принадлежащая циклу, используется только один раз (за исключением начальной и конечной вершин, которые совпадают).

Например, пути m1 и m3 являются простыми циклами, а путь m2 не является простым циклом, так как вершина x1 используется в нем дважды.

Простой цикл, проходящий через все вершины графа, имеет особое значение и называется гамильтоновым циклом. Конечно, не все графы обладают гамильтоновыми циклами. Так, например, путь m3 является гамильтоновым циклом графа, приведенного на рис. 3.1, а граф на рис. 3.2 не имеет гамильтонова цикла. В отличие от эйлерового цикла для гамильтонова цикла неизвестен простой критерий его существования в произвольном графе.

Контуром называется цикл в ориентированном графе. Таким образом, контур является путем
(x1, x2,..., xq), в котором совпадают начальная и конечная вершины, т. е. в котором x1 = xq.

На рис. 3.3 маршруты

, и

являются контурами.

Цикломатическим числом графа n (G) называется число независимых простых циклов, содержащихся в графе. Оно вычисляется по формуле:

n (G) = mn + 1. (3.1)

Например, количество независимых контуров электрической цепи определяется цикломатическим числом.

 

 

Теорема о пяти красках.

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

Гипотеза о четырех красках

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

 

Гиперкубы

Гиперкубом (n-мерный куб) Hn называется граф, каждая вершина которого взаимнооднозначно соответствуют области пространства и 2 вершины соединены ребром, если они соответствуют соседним областям.

Свойства:

1) h(Hn) = 2 (2 цвета вершин)

2) Гиперкуб используется для вложения в производные графов с целью определения характеристик последних.

H(Hn) = n (цвет ребер)

Максимальная длина цепи: lmax = 2n-1; d(Hn) = n;

Запрещенными фигурами для вписания графа в гиперкуб являются графы с циклами нечетной длины и К23.

Граф называется вложенным в булевое пространство или кубируемым, если существует взаимнооднознозначное соответствие между вершинами графа и гиперкубом. Граф, который не вписывается в гиперкуб – некубируемый.

Число цепей, которое соединяет 2 произвольные вершины гиперкуба равняется n!

 

Метод Квайна-Мак-Класки

Исходная функция представляется в СДНФ

1 Шаг. Нахождение первичных импликант.

Все элементарные конъюнкции сравниваются попарно

Если встречаются 2 конъюнкции ранга i вида , то они образуют элементарную импликанту ранга i-1

Импликанта i ранга, принимающая участие в организации простой импликанты i-1 ранга помечается, а все неотмеченные импликанты называются простыми или первичными.

В результате получим 9 импликант ранга 3 а импликант ранга 4 не осталось.

В результате попарного сравнения импликант ранга 3 мы выделили 1 импликанту ранга 2 и осталось 5 простых импликант ранга 3.

2 Шаг. Расстановка меток.

Для построения таблицы покрытия нужно выбрать минимальное число первичных импликант.

Составляется таблица, число строк равно чису простых импликант ранга 3.

В столбцах присутствуют все импликанты ранга 4, не покрываемые импликантами ранга 2. В таблице покрытий ставятся метки на пересечение столбца конъюнкции i-го ранда и входящей в нее простой импликанты меньшего ранга.

3 Шаг. Нахождение существенных импликант

Если в каком-то из столбцов составленной таблицы имеется только 1 метка, то первичный импликант, стоящий в соответствующей строке, называют существенным импликантой и она не может быть исключена из первой части ДНФ.

Производится покрытие столбцов строками. При этом выбирается такая совокупность первичных импликант, которая включает метки во всех столбцах.

Полнота логических функций.

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

ТЕОРЕМА: для полноты любого набора булевых операций необходимо и достаточно чтобы с помощью операций этого набора можно было построить функцию и одну из функций xy или .

Существует 7 полных наборов булевых функций:

1) (&, ) «и не» конъюнктивный базис Буль;

2) () «или не» дизъюнктивный базис Буль;

3) { | } – Шеффер;

4) { } – базис Пирса;

5) { , 0} -

6) { , } – импликативные базисы (5, 6);

7) { , &} – базис Жигалкина;

При этом можно переходить из одного базиса в другой.

Продолжение.

Наиболее распространенным способом задания автомата является таблица переходов и таблица выходов. На пересечении i-й строки и j-го столбца таблицы переходов указывается то внутренне состояние, в которое автомат перейдет из внутреннего состояния Si (i-я строка) под действием входных сигналов, соответствующих состоянию входа Xj (j-й столбец).
Синтез абстрактного автомата заключается в получении таблицы переходов и таблицы выходов или графа. Далее осуществляется структурный синтез, цель которого состоит в построении схемы, реализующей автомат из заданных логических элементов.

 

Геометрический (графический)

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

Теоретико-множественный


Матричный

а) Матрица инцидентности

n-число вершин, m – число дуг или ребер

Для неорграфа:

б) Матрица смежности

Неорграф:

Орграф:

Маршруты, цепи, циклы

Маршрутом в графе называется {x1,r1,x2,r2,…xn}

чередующиеся последовательность вершин и ребер/дуг.

Неорграф:

Цепью ρ=(r1, … rn) называется упорядоченная последовательность ребер в которой у каждого ребра ri одна из граничных вершин является граничной вершиной ri-1, а другие ri+1. Если вершины и ребра в цепи различны, то маршрут называют простой цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь называется простым циклом.

Орграф:

Путем в графе называется упорядоченная последовательность дуг μ = (U1, …, Un), в которой конец предыдущей дуги совпадает с началом последующей. Путь у которого начальные и конечные вершины совпадают – контур. Длина цепи – число ребер в цепи. Граф называется связным, если любая пара его вершин соединены цепью. Минимальная длина цепи, соединяющая вершины xi и xj называется расстоянием. Максимальное расстояние между вершинами графа называется диаметром графа. . Цепь (неорграф) называют составной, если в ней повторяется хотя бы одно ребро; сложной, если повторяется хотя бы одна вершина. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа ровно 1 раз. В орграфе путь, проходящий через все вершины ровно 1 раз, называется гамильтоновым, если у него начальная и конечная вершина совпадают, то гамильтонов контур.

 

 

Алгоритм Дейкстры.

Пусть l (xi) – пометка вершины xi.

Шаг 1. Присвоение начальных значений. Положить l* (s) = 0 и считать эту пометку постоянной. Положить l (xi) = ∞ (бесконечность) для всех xi ¹ s и считать эти пометки временными. Положить р=s.

Шаг 2. Обновление пометок. Для всех вершин xi Î Г (р), имеющих временные пометки, изменить пометки в соответствии с выражением:

l (xi) = min{ l (xi), l (p) + c (p, xi)}. (2.3)

Шаг 3. Превращение пометки в постоянную. Среди всех вершин с временными пометками найти такую, для которой l* (xi) = min{ l (xi)}.

Шаг 4. Считать пометку вершины xi* постоянной и положить p = xi*.

Шаг 5. Если р=t, то l* (р) является длиной кратчайшего пути. Конец.
Если р ¹ t, перейти к шагу 2.

Как только длина кратчайшего пути от s до t будет найдена [она будет постоянной пометкой вершины l* (t)], сами пути можно получить с помощью рекурсивной процедуры. Так, для вершины xk, непосредственно предшествующей вершине t в кратчайшем пути от s к t, будет соблюдаться отношение: l* (xk) + c (xk, t) = l* (t).

Таким образом, для любой вершины xi можно найти предшествующую вершину xk, принадлежащую пути m (s, t), для которой справедливо:

l* (xk) + c (xk, xi) = l* (xi). (2.4)

Если существуют несколько кратчайших путей от s к t, то данное соотношение будет выполняться для нескольких вершин. В этом случае выбор пути может быть произвольным.

 



Поделиться:


Последнее изменение этой страницы: 2017-01-19; просмотров: 160; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.229.173.107 (0.13 с.)