Реферат: Элементы комбинаторики. Правила умножения и сложения

1. Элементы комбинаторики. Правила умножения и сложения.

Комбинаторика – раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых их элементов заданного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос: «Сколькими способами?» Многие комбинаторные задачи могут быть решены с помощью следующих 2х важных правил, называемых соответственно правилами умножения и сложения.

Правило умножения .

Если из нек множ первый объект (элемент х) можно выбрать n1 способами и после каждого такого выбора второй объект (элем у) можно выбр n2 способами, то оба объекта (х и у) в указ порядке можно выбрать n1*n2 способами.

Это правило распр-ся на случай трех и более объектов.

Пример : сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если: а) числа не повт; б) числа могут повтор.

Решение: а) 1ую цифру выбираем 5мя способами, 2ую – 4мя, 3 – 3мя 5*4*3=60 способов

б) 5*5*5=125 сособов

Правило сложения

Если некот объект х можно выбр n1 способами, а объект у можно выбр n2 способами, причем первые и вторые выборы таковы, что они взаимно искл друг друга и не могут быть получены одновременно, то объект хUу (х или у) можно выбр n1+n2 способами.

Пример : Четыре города M,N,P,K соединены дорогами так, что из Mв Nведут 5дорог, из N в K– 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги.

Сколькими способами можно проехать из М в К?

Решение: Из М в К через N ведут 5*6=30 дорог, Из М в К через P ведут 4*3=12 дорог

Из М в К ведут 30+12=42 дороги.

2. Размещения, перестановки, сочетания.

Размещениями из n-элементов по m элементов в каждом называются такие комбинации, из которых каждая содержит mэлементов из данных n элементов, и которые отличаются друг от друга порядком их следования, либо самими элементами.

Если элементы комбинации не повторяются.

Размещениями из n-элементов по m элементов с повторениями называются такие комбинации, в которых каждая содержит mэлементов из данных n элементов, записанных в каком нибудь порядке, причем один и тот же элемент может входить в комбинацию более одного раза.

Размещения с повторениями обозначаются Ã и вычисляются по формуле:

Примеры в 1ом вопросе!

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

Пример: Имеется 5 равных геом фигур: 3 желтых и 2 белых круга. Сколько различных узоров можно составить из этих кругов, располагая их в ряд?

Решение: Желтые круги будут повт 2! раз

Белые - 3! раз

Число разл узоров будет равно 5!/2!*3!=10

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

Где

Сочетаниями из n-элементов по m элементов в каждом называются такие комбинации, каждая из которых состоит из mэлементов, выбранных из данных n элементов, и которые отличаются друг от друга хотя бы одним элементом.

Пример: Сколькими способами можно выбрать 3 представителей учебной группы в студ совет, если в группе 25чел.

Сочетаниями из n-элементов по m с повторениями назыв такие комбинации, каждая из которых состоит из mэлементов из данных n элементов, причем один и тот же элемент может входить в комбинацию более одного раза.

Обозначается – Č и вычисл по форм:

3. Бином Ньютона.

Бином Ньютона – это формула, представляющая выражение в виде многочлена.

Она имеет вид:

Её можно записать иначе:

, где - число сочетаний из nэлементов по k,

Известные формулы сокращенного умножения: квадрат суммы, квадрат разности, куб суммы, куб разности являются частными случаями бинома Ньютона.

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

Любой элемент треугольника паскаля, распол в n-ой строке на k-ом месте выражает ,

Где отчет nведется от 1, а отчет k ведется от 0.

Пример : Представить в виде многочлена

Решение:

4. Булевы функции. Определение. Примеры.

Алгебра логики, выстроенная в XIX веке, долго существовала как абстрактная, хотя и очень красивая наука. Но в середине XX века оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в настоящее время служит основой для описания логики работы аппаратных и программных средств ЭВМ. Она ис­пользует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично и ЭВМ использует лишь сигналы 0 и 1, воспринимая их как логические переменные.

Рассмотрим множество В = {0;1}.

Тогда В² = {(0;0),(0;1),(1;0),(1;1). Снимем разделительный к внутри каждой пары и уберём скобки. Тогда В² = {00, 01,10,11}. Аналогично В³ = Вх В² ={000,001,010,011,100,101,110,111} и т. д.,

Каждому элементу множества В ⁿ поставим в соответствие единст­венный элемент множества В - {0; 1}. Полученное соответствие наз булевой функцией . Элементы множества В ⁿ являются значениями аргумента булевой функции. Они представляют собой наборы, состоящие из нулей и единиц, и называются кортежами. Длиной кортежа назы­вается число цифр, образующих кортеж. Множество В ⁿ - область определения функции

Множества значений булевой функции, вообще говоря это значение функции В = {0;1}.

Задание булевой функции в виде таблицы, в которой указаны значения каждой переменной кортежа и значение самой функции, называется заданием таблицей истинности или матричным заданием булевой функции.

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

Область определения D ( f ) булевой функции n = 1 это совокупность двух точек 0 и 1 числовой прямой, т.е. одномерного куба

Если п = 2, то D ( f ) = {00,01,10,11}- это множество вершин квадрата, т. е. двухмерного куба

Если п = 3, то D ( f ) = {000,001,010,01 1,100,101,110,111}

множество вершин трёхмерного куба в декартовой системе координат.

На кортежах длины n можно составить различных простейших булевых функций.

Если n=1, то число простейших булевых функций равно 4, если n=2, то их 16, если n=3, то их 256

Если n=1, то существует 4 простейших булевых функций:

- константа 0(тождественный 0)

- константа 1(тождественная 1)

- тождественная функция

- отрицание

5. Реализация булевых функций формулами.

0	0	1	1	0	0	1	0
0	1	1	0	0	1	1	0
1	0	0	1	0	1	0	1
1	1	0	0	1	1	1	0

0	0	1	0	1	0	0	1
0	1	0	1	0	1	0	1
1	0	1	0	0	1	0	1
1	1	1	0	1	0	0	1

, - отрицание

- конъюнкция (логическое умножение)

- дизъюнкция

- импликация

- отрицание импликации

- эквиваленция

- сумма по модулю 2

- стрелка Пирса

‌‌‌ ‌‌‌‌‌‌│ - штрих Шеффера

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

Самой старшей считается «отрицание»

Затем – «конъюнкция», «штрих Шеффера», «стрелка Пирса»

Затем – «дизъюнкция»

Затем – «импликация»

На самом низком уровне – эквиваленция и сумма по модулю 2.

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

Итак, стрелка Пирса равна антидизъюнкции, штрих Шеффера равен антиконъюнкции.

Любую булеву функцию можно представить с помощью отрицания, конъюнкции и дизъюнкции.

6. Совершенная конъюнктивная нормальная форма.

Представление булевой функции в виде конъюнкции несовпадающих элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ) этой функции.

Пример

Это конъюнкция трех несовпадающих элементарных дизъюнкций.

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

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

Если каждая входящая в КНФ элементарная дизъюнкция является полной относительно набора , то КНФ называется совершенно конъюнктивной нормальной формой (СКНФ)

Пример:

Любую булеву функцию , не равную тождественной единице, можно представить в виде СКНФ.

Получить СКНФ можно преобразовывая формулы, а можно по таблице истинности.

7. Совершенная дизъюнктивная нормальная форма.

Представление булевой функции в виде дизъюнкции несовпадающих элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) этой функции.

Пример

Одна третья конъюнкции является полной элементарной.

Чтобы из неполной элементарной конъюнкции получить полную необходимо неполную элемент конъюнкцию логически умножить на 1, а 1 представить в виде дизъюнкции недостающей переменной и её отрицания. После этого необходимо применить дистрибутивный закон.

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

Если каждая входящая в ДНФ элементарная конъюнкция является полной относительно набора , то ДНФ называется совершенно дизъюнктивной нормальной формой (СДНФ)

Пример:

Получить СДНФ можно преобразовывая формулы, а можно по таблице истинности.

8. Переключательные функции. Способы задания.

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

Основы перекл функций заложил англ матем Дж.Буль в 19 веке.

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

Отсутствие сигнала как на входе, так и на выходе будет сигнализировать 0, наличие – 1.

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

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

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

НЕ ПОЛНОСТЬЮ!!!!

9. Переключательные функции от 2-х и п переменных.

Переключательные функции от 2х переменных – это булевы функции двух переменных.

10. Определение и примеры функционально полных базисов.

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

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

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

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

Заметим, что в силу законов де Моргана:

Дизъюнкцию можно представить через конъюнкцию и отрицание. Следовательно, функционально полной является система функций и (конъюнкция и отрицание).

Также конъюнкцию можно представить через дизъюнкцию и отрицание. Следовательно, функционально полной является система функций и (дизъюнкция и отрицание).

Итак, примеры функциональных систем:

Системы F3 и F4 являются базисами, т.к. удаление из них любой функции приводит к системе, не являющейся полной.

11. Специальные разложения переключательных функций.

Любую перекл функцию кроме тожд нуля можно представить в виде СДНФ. А в свою очередь, любую функцию, представленную в виде СДНФ, можно представить с помощью суммы по модулю 2, конъюнкции и константы 1. Т.е. любую перекл функцию можно представить с помощью функций: сумма по модулю 2, конъюнкция и константы 1. Отсюда следует, что система функций явл полной.

Более того эта система является еще и базисом.

Базис называется системой Жегалкина.

Теорема.Каждая перекл функция единственным образом допускает представление в виде полинома Жегалкина.

Пример: . Представим эту функцию в виде полинома Жегалкина.

Решение

Другим, более распространенным способом нахождения полинома Жегалкина явл метод неопределенных коэффициентов, который основан на выше указанной теореме

12. Классы Поста. Теорема о функциональной полноте.

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

Существуют 5 классов перекл функций. Это классы Поста (Пост – Америк логик 20 века.

1. Класс линейных функций

Перекл функция назыв линейной, если она представима полиномом Жегалкина первой степени:

Число линейных функций рано например при n=2 число линейных функций равно 8:

2 . Класс функций, сохраняющих 0

Если перекл функция на кортеже 00…0 равна нулю, то говорят, что функция сохран нуль

Т.о. функция принадлежит классу функций, сохраняющих 0, если

Для 2х переменных таких функций 8.

3 . Класс функций, сохраняющих 1

Если перекл функция на кортеже 11…1 равна 1, то говорят, что функция сохран единицу

Т.о. функция принадлежит классу функций, сохраняющих 1, если

Для 2х переменных таких функций 8

4. Класс монотонных функций

- монотонная функция

Таких функций 6

5. Класс самодвойственных функций.

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

На кортежах 00 и 11,01,10 противоположные значения могут иметь функции

Теорема Поста о функциональной полноте. Для того чтобы система булевых функций была полной необходимо и достаточно, чтобы она содержала:
-хотя бы одну функцию, не сохраняющую 0

-хотя бы одну функцию, не сохраняющую 1

-хотя бы одну функцию, не явл линейной

-хотя бы одну функцию, не явл монотонной

-хотя бы одну функцию, не явл самодвойственной.

Каждый базис содержит не более 4х булевых функций.

13. Минимизация переключательных функций. Основные понятия,

14. Способы построения минимальных ДНФ.

Минимизация ДНФ включает следующие этапы:

1. Получение простых импликант и сокращенной ДНФ
2. Получение тупиковой ДНФ
3. Выбор из тупиковых ДНФ минимальной

Для реализации первого этапа алгоритма будем применять один из след методов: Метод Квайна, геометрический, карты Карно

Метод Квайна

В его основе лежат следующие равносильности:

1. Полного склеивания

2. Поглощения

3. Не полного склеивания

Если в СДНФ провести все операции неполного склеивания (тем самым усложнив СДНФ), а затем провести операции поглощения, то получится сокращенная ДНФ.

Геометрический метод

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

Суть метода: 1) для функции nпеременных отмечаются вершины куба, соответств кортежам, на которых функция принимает значение 1.

2) проводят склеивание – отмечают ребра, содерж 2 отмеч вершины.

3) проводят поглощение – отмечают грани, содерж все 4 склеенные вершины.

Цель действий – накрыть множество, всех отмеченных вершин, как можно меньшим числом граней, ребер.

Карты Карно

Могут быть использованы для минимизации булевой функции любого числа переменных. Но наиболее удобно использовать его, если n=3 или n=4

Переменные кортежа разбиваются на 2 части. Первая часть является кодом столбца, вторах – строк. Таким образом, карты Карно неявно задают сами кортежи.

Например:

Процесс минимизации СДНФ представляет собой склеивание кодов кортежей для каждого сплошного участка причем колво единиц на таком сплошном участке должно быть степенью числа 2.

15. Понятие графа. Виды графов. Изоморфизм.

Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты удобно изображать точками системы, связи между ними – дугами со стрелками(или без них). Такие системы образ графы. Объекты называют вершинами, дуги – ребрами графа.

Графом G называется совокупность 2х конечных множеств V(множество вершин) и E(множество ребер), между элементами которых определено отношение инцидентности. Каждое ребро инцидентно 2м вершинам , которое оно соединяет.

Граф, содержащий направленные ребра (дуги), называется ориентированным (орграфом). Если ребра не имеют направлений, то граф называют не ориентированным.

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

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

Ребро, концевые вершины которого совпадают, называют петлей.

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

Степенью вершины в неориентир графе называется колво ребер, инцидентных этой вершине.

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

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

16. Способы задания графов.

В общем виде «задать граф» означает: описать множество его вершин и ребер, а также отношение инцидентности.

Способы задания графа:

1. Графический

2. Перечислением вершин и ребер.

3. Задание графа матрицей инцидентности. Строки матрицы характеризуют вершины графа, столбцы – ребра графа.

Для неориентир графа: 1 – если вершина и ребро инцидентны, 0 – если не инциндентна.

Для ориентир - -1 если вершина является началом ребра, 1 – если концом ребра, 0 – не инциндентны, 2 – ребро – петля.

4. Задание графа матрицей смежности.

Матрица смежности – это квадратная матрица размера n*n, которая по горизонтали и по вертикали учитывает все вершины графа.

Матрица смежности не ориентир графа симметрична относительно главной диагонали. И колво ребер графа равно сумме элементов матрица, распол выше главной диагонали.

5. Задание графа матрицей весов.

Матрица весов - вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n n (n - число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v , v), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи.

17. Маршруты и циклы. Связность.

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

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

Маршрут называется замкнутым, если . Незамкнутым - если

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

Граф, у которого любые 2 его вершины являются смежными, называется полным графом.

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

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

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

Отношение связности – это отношение эквивалентности.

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

Ребро называют перешейком, если после его удаления граф теряет свойство связности, т.е. распадается на 2 компонента связности.

Ориентированный граф называют сильно связным, если 2 любые его вершины, можно соединить путем, т.е. и

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

18. Эйлеровы и гамильтоновы графы.

Путь в графе называется эйлеровым, если он содержит все ребра графа. Замкнутый эйлеров путь называется эйлеровым циклом. Граф, который имеет эйлеров цикл, также называется эйлеровым.

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные.

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

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

Если в простом графе G(V,E) с pвершинами степень любой вершины v удовлетворяет неравенству p(v)≥p/2

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

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

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

Любой граф изоморфный плоскому графу, называется планарным.

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

Очевидно, что 1) всякий подграф планарного графа планарен.

2) граф планарен, тогда и только тогда, если каждая связная компонента этого графа – планарный граф.

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

Теорема Понтрягина-Куратовского.

Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К₅ или К_3.3

20. Формула Эйлера.

Формула Эйлера:

n-m+p=2, где n-число вершин, m – ребер, p-граней.

Следствие: Если в простом связном плоском графе n≥3, то m≤3n-6

Формулой Эйлера удобно пользоваться при исследовании графа на планарность.

21. Раскраска графов.

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

Раскраской графа называется такое приписывание цвета его элементам (вершинам, рёбрам или граням), что никакие два смежные элемента не получают одинакового цвета.

Хроматическим числом элементов (вершин, рёбер или граней) графа рыпается минимальное число цветов для раскраски элементов графа.

В конце XIXвека была сформулирована гипотеза четырёх красок: всякий планарный граф 4-раскрашиваем. Попытки доказать эту гипотезу привели к следующей теореме: ВСЯКИЙ ПЛАНАРНЫЙ ГРАФ 5-РАСКРАШИВАЕМ.

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

22. Деревья. Минимальное остовное дерево.

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

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

Лесом называется любой граф без циклов.

Следовательно, деревья являются компонентами леса.

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

Если дерево имеет п вершин, то оно имеет п-1 ребро

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

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

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

С - лес, который на любой связной компоненте графа G образует дерево. Если G - связный граф, то остов G является деревом, которое будем называть остовным деревом графа G.

Граф может иметь несколько остовов.

Обратим внимание, что ВСЕ ОСТОВЫ одного графа имеютОДИНАКОВОЕ ЧИСЛО РЁБЕР, НО ИХ ВЕС НИ ЯВЛЯЕТСЯ ВеличинойПОСТОЯННОЙ ДЛЯ ДАННОГО ГРАФА, ЗАВИСИТ ОТ ВЕСОВ ВЫЬРАнНЫХ ребер.

23. Жадный алгоритм.

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

Один из эффективных способов решения поставленной задачи —реш ение с помощью алгоритма Краскала или «жадного алгоритма».

Жадный алгоритм:

1. Необходимо упорядочить множество весов
2. выбрать ребро наименьшего веса и инцидентные ему вершины и включит их в остовное дерево.
3. Исключить выбранное ребро из списка рёбер
4. повторяем шаг 2 и3 пока не построим все вершины
5. посчитать все полученного остовного дерева.

24. Алгоритм Прима.

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

Один из эффективных способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма».

Алгоритм Прима или, как его ещё называют, алгоритм ближайшего соседа.

Анализируем матрицу весов. Начинаем с произвольной вершины v_i

Шаг 1. Изучая i-ю строку матрицы весов, выбираем ребро, инцидентное v_i и имеющее наименьший вес. Выбранное ребро ( v_i v_j - первое ребро остова. Удаляем его из матрицы весов.

Шаг 2. Изучая i-ю и .j-ю строки матрицы весов, выбираем ребро минмального веса, инцидентное одной из двух вершин. Присоединяем выбранное ребро к остову и удаляем из матрицы весов.

И так далее. Процесс повторяется до тех пор, пока в остов не будут включены все вершины графа.

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

Алгоритм Дейкстры позволяет, решить задачу о нахождении кратчайшего пути в графе.

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

26. Понятие потока в сети.

Примеры сетей и потоков в них: потоки автом транспорта в сети автодорог, поток грузов по железнодорожн сети, поток телегр сообщений в сети связи и т.д. Все эти сети имеют огранич ресурс( поток ограничен сверху).

Ориентир граф называется сетью, если он удовлетвор след условиям:

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

Функция φ, определенная на множестве дуг сети, называется допустимым потоком, если:

для любой дуги e_i выполнено условие 0≤φ≤с(e_i )

т.е. для любой дуги допустимый поток не превышает её пропускной способности.

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

Величина называется остаточной пропускной способностью дуги.

Дуга e_i называется насыщенной, если (если допустимый поток равен пропускной способностью)

Суммарный поток, вытекающий из источника, равен суммарному потоку, втекающему в сток. Этот поток будем называть потоком в сети.

27. Полный и максимальный потоки в сети.

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

Поток называется максимальным , если он принимает максимальное значение по сравнению с остальными потоками в сети.