Лекции по прикладной математике - файл n1.doc

Лекции по прикладной математике
скачать (24.4 kb.)
Доступные файлы (1):
n1.doc116kb.06.04.2007 18:42скачать

n1.doc

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


  1. (X?Y)۸Z?X




X

Y

Z

X?Y

(X?Y)۸Z

(X?Y)۸Z?X

0

0

0

0

0

1

0

0

1

1

1

0

0

1

0

0

0

1

0

1

1

1

1

0

1

0

0

0

0

1

1

0

1

0

0

1

1

1

0

0

0

1

1

1

1

1

1

1




  1. X۸Y?Y۷X?X?Y




1

2

3

4

5

6

7

8

9

X

Y

Y

X۸Y

4

5?Y

6۷X

7?X

8?Y

1

1

0

0

1

0

1

1

1

1

0

1

1

0

0

1

1

1

0

1

0

0

1

0

0

1

0

0

0

1

0

1

1

1

0

1


2. Электрическая цепь с одной электрической лампой и ключами.
Комитет состоит из трех членов. Надо спроектировать электрическую цепь показывающую результаты голосования, каждый член нажимает кнопку, если голосует да, и не нажимает, если голосует против. Если предложение принято большинством голосов, то зажигается лампочка.
(X۸Y)۷(X۸Z)۷(Y۸X)۷(Y۸Z)۷(Z۸X)۷(Z۸Y)
















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

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

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














Рис. 1 Рис. 2


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

Ребро, концевые вершины которого совпадают, назы­вается петлей. На рис. 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



Теорема 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.




Рис. 4

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
















Рис. 5
Рангом графа G, имеющего n вершин и состоящего из k компонент, называется число r (G) = n - k.

Цикломатическим числом графа называется число µ (G) = mn + 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 Рис. 7
Теорема 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) не является циклом.






Рис. 8 Рис. 9

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

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





а1

а2

а3

а4

а5







а1

а2

а3

а4

а5

а6

р1

1

0

-1

1

0




р1

1

1

0

0

0

0

р2

-1

1

0

0

0




р2

0

1

1

0

1

1

р3

0

-1

1

-1

1




р3

0

0

0

0

0

1

р4

0

0

0

0

-1




р4

0

0

0

1

1

0






















р5

1

0

1

1

0

0


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

Матричное представление графа является наиболее удобной формой задания графа при вычислениях на машине.
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.

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


1. Таблицы истинности
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации