Таблицы истинности

Размещено на http://www.allbest.ru

1. Таблицы истинности

(X>Y)?Z>X

X?Y-Y?X>X>Y

2. Электрическая цепь с одной электрической лампой и ключами

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

3. Конспект

1. Определение графов

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

На рис. 1 изображен граф, имеющий пять вершин и шесть ребер.

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

Ребра, имеющие одинаковые концевые вершины, называются параллельными.

Ребро, концевые вершины которого совпадают, называется петлей. На рис. 1 а4 и а5 - параллельные ребра, а а2 - петля.

Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. На рис. 1 вершина р3 и ребро а3 инцидентны друг другу.

Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инцидентные одной и той же вершине, называются смежными ребрами. На рис. 1 р1, р 2 - смежные вершины, а а1, а4 - смежные ребра.

Степенью вершины называется число ребер, инцидентных ей. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. На рис. 1 степень вершины р1 равна трем, р4 - висячая вершина, р5 - изолированная.

Теорема 1. В графе сумма степеней всех его вершин - число четное, равное удвоенному числу ребер графа:

матрица инциденция электрический

где n - число вершин графа, а т - число его ребер.

Теорема 2. Число нечетных вершин любого графа, т. е. вершин, имеющих нечетную степень, четно.

Граф называется полным, если любые две его различные вершины соединены ребром, и он не содержит параллельных ребер.

Дополнением графа G называется граф G с теми же вершинами, что и граф G, и содержащий только те ребра, которые нужно добавить к графу G, чтобы получился полный граф. На рис. 2 изображены следующие графы: G1 - полный граф с пятью вершинами, G2 - некоторый граф, имеющий пять вершин, G2 - дополнение графа G2

Путем в графе называется такая последовательность ребер, ведущая от некоторой начальной вершины р1 в конечную вершину рп, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Например, в графе, изображенном на рис. 1, последовательность ребер (а1, а2, а3, а4, а5, а6) образует путь, ведущий от вершины р1 к вершине р4.

Циклом называется путь, начальная и конечная вершины которого совпадают. На рис. 1 ребра (а1, а3, а4) образуют цикл.

Цикл графа называется простым, если он не проходит ни через одну вершину графа более одного раза.

Длиной пути, или цикла называется число ребер этого пути или цикла.

2. Виды графов.

2.1 Деревья.

Связный граф, не содержащий циклов, называется деревом.

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

Кодеревом Т* остова Т графа называется такой подграф, который содержит все его вершины и только те ребра, которые не входят в Т.

На рис. 3 представлены граф G, его дерево G1, остов Т1 и кодерево Т1*.

Теорема 3. Граф G с n вершинами является тогда и только тогда, когда G -связный граф и число его ребер равно (n - 1).

Ребра остова Т называются ветвями графа G, а ребра кодерева - Т* -связями.

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

2.2 Лес.

Граф, не содержащий циклов и состоящих из k компонентов, называется k - деревом; k - дерево графа G, содержащее все его вершины, называется остовным.

Подграф G, содержащий все его вершины и только те ребра, которые не входят в остовное k - дерево Т графа G, называется k - кодеревом Т*.

Если граф G содержит k компонент, то его остовное k - дерево Т называется лесом, а k - кодерево Т* в этом случае называется КО - лесом.

На рис. 4 изображены остовное 2 - дерево Т и 2 - кодерево Т* графа G, представленного на рис. 3.

На рис. 5 представлен граф G, содержащий две компоненты, его лес Т и КО - лес Т*.

Рангом графа G, имеющего n вершин и состоящего из k компонент, называется число r (G) = n - k. Цикломатическим числом графа называется число µ (G) = m - n + k, где m - число ребер графа G. Очевидно, что ранг и дипломатическое число связаны следующим соотношением;

r (G) + µ (G) = m

Теорема 5. Ранг r (G) графа G равен числу ребер леса, а цикломатическое число µ (G) равно числу ребер КО - леса.

2.3 Разрезы.

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

Пусть есть некоторый связный граф G, множество вершин которого разбито на два непустых непересекающихся подмножества Р = Р1 U Р2. Тогда множество всех ребер G, имеющих одну концевую вершину в Р1, а другую - в Р2, называется разрезом графа G.

3. Пути (циклы) графов.

3.1 Эйлеровы графы.

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

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

На рис. 6 граф G не является эйлеровым, так как вершина р3 инцидентна только одному ребру. Если путь приведет в вершину р3, то не будет ребра, по которому можно было бы выйти из р3 .

Теорема 6. Граф G является эйлеровым тогда и только тогда, когда G -связный и все его вершины имеют четную степень.

Граф G, изображенный на рис. 7, является эйлеровым. Последовательность ребер (а1, а2, а3, а4, а5, а6, а7, а8, а9, а10) образует эйлеров цикл.

Теорема 7. Граф G обладает эйлеровым путем с концами р1, р2 тогда и только тогда, когда G - связный и р1, р2 - единственные его вершины нечетной степени.

На рис. 6 изображен граф G, обладающий эйлеровым путем (а1, а2, а3, а4, а5, а6) с концевыми вершинами р5, р6.

3.2 Гамильтоновы графы.

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

Граф, обладающий гамильтоновым циклом, называется гамильтоновым.

Критерий существования гамильтонова цикла в произвольном графе G еще не найден. Достаточным условием существования гамильтонова цикла является полнота графа G.

Граф, изображенный на рис. 6, не является гамильтоновым, а граф, представленный на рис. 8, содержит гамильтонов цикл (а1, а2, а4, а5, а6).

3.3 Ориентированные графы.

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

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

В ориентированных графах циклом называется путь, начало и конец которого совпадают. На рис. 9 дуги (а1, а4, а5) образуют цепь, а дуги (а1, а2, а5) - путь. Последовательность дуг (а1, а2, а3) составляет цикл, а последовательность (а1, а2, а4) не является циклом.

Цепь, путь, цикл в произвольном графе G называются простыми, если они не проходят ни через одну свою вершину более одного раза,

Длиной цепи, пути, цикла называется число содержащихся в них дуг.

4. Матрицы графов.

Граф может быть задан разными способами: рисунком, перечислением вершин и ребер (или дуг) и т. д. Одним из самых удобных способов является задание графа с помощью матрицы. Пусть некоторый граф G имеет п вершин р1, р2, ……. рn и т ребер а1, а2, ……. am. Построим матрицу, имеющую п строк и m столбцов. Каждая строка матрицы будет соответствовать вершине, а столбец - ребру графа. В столбце aj все элементы, кроме двух, будут равны нулю. Для ориентированного графа в строке, соответствующей начальной вершине дуги aj, ставят число +1, а в строке, соответствующей конечной вершине, - число -1. Для неориентированного графа в строчках матрицы, соответствующих концевым вершинам ребра aj, ставят 1, а в остальных строчках - 0. Для графов, изображенных на рис. 9 и 6, матрицы имеют соответственно следующий вид:

Построенные матрицы называются матрицами инциденций графа.

Матричное представление графа является наиболее удобной формой задания графа при вычислениях на машине.

5. Алгоритм и построение графов.

Существует множество вариантов алгоритмов построения графов. Перечислим некоторые из них:

Максимальные потоки в сети:

Алгоритм нахождение увеличивающей цепи;

Алгоритм отыскания максимального потока в сети.

Задачи о кратчайшем пути между двумя вершинами графа:

Алгоритм поиска кратчайшего пути.

Алгоритм построения деревьев:

Алгоритм построения минимального покрывающего дерева.

Задачи сетевого планирования:

Алгоритм получения правильной нумерации вершин;

Алгоритм расчета ранних сроков начал и окончаний работ;

Алгоритм построения критического пути;

Алгоритм вычисления поздних сроков наступления событий.

Рассмотрим один из алгоритмов:

Алгоритм отыскания максимального потока в сети:

Данный алгоритм, использующий увеличивающие цепи, называется алгоритмом Форда. Он состоит из следующих шагов.

1. Выбирают некоторый поток f (а) из s в t (например, f (а) ? 0).

2. Находят классы увеличивающих (А+) и уменьшающих (А-) дуг.

3. Применяют алгоритм поиска увеличивающей цепи из s в t. Если такой цепи нет, то поток f - максимальный. Если цепь С найдена, то перейти к шагу 4.

4. Находят min (Дf (б)), min f (б).

5. Пусть д > 0 - наименьшее из этих чисел.

6. Увеличивают поток вдоль цепи С на д и переходят к шагу 2.

Очевидно, что построенный таким образом поток удовлетворяет следующим условиям:

f (б) ? с(б), div f (p)=0 при p = s, p=t.

Этот поток является максимальным. Если начальные данные целочисленны, то выполнение алгоритма Форда завершается за конечное число шагов.

Размещено на Allbest.ru