Для чего нужен и как работает алгоритм Краскала?

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

Шаг 1: выберем ребро с наименьшим весом.

Шаг 2: среди оставшихся рёбер выберем ребро с наименьшим весом.

Шаг 3: среди оставшихся рёбер выберем ребро с наименьшим весом, не образующее цикла с рёбрами, выбранными ранее. Шаг 3 повторяется до тех пор, пока не будет выбрано n- 1 ребро. Выбранные n- 1 ребро образуют минимальный каркас.

Обоснование алгоритма. Необходимо убедиться, что шаг 3 возможен, пока не выбрано n-1 ребро. Рассмотрим произвольный момент в работе алгоритма. Допустим, уже выбранные рёбра вместе с инцидентными им вершинами образуют несвязный граф. Тогда добавление ребра, соединяющего компоненты связности (такое существует, ведь исходный граф связен), не приведёт к образованию цикла. Если уже выбранные рёбра образуют связный граф, то обязательно есть свободная вершина – так как если заняты все вершины, то, по теореме 1, выбрано уже n-1 ребро. Добавление ребра, инцидентного свободной вершине, конечно, не приведёт к образованию цикла. Итак, шаг 3 всегда возможен. Если выбрано n -1 ребро, то они обязательно образуют связный граф – иначе, добавляя рёбра, мы получим дерево с n вершинами и большим, чем n -1 числом рёбер.

24. Какой граф называется плоским (планарным)? Приведите пример неплоского графа.

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

25. Сформулируйте критерий планарности графа (теорема Понтрягина-Куратовского).

Теорема 5 (теорема Понтрягина–Куратовского). Граф является плоским тогда и только тогда, когда в нём нет подграфа, который можно «сжать» до одного из графов, рассмотренных в следствиях 1 и 2.

Сжатие графа – это удаление вершины степени 2 и замена двух инцидентных ей рёбер одним ребром

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

26. Сформулируйте и докажите теорему Эйлера.

Теорема 4 (теорема Эйлера). Пусть В, Р, Г – число вершин, рёбер и граней соответственно. Тогда для любого плоского связного графа В – Р + Г = 2.

Доказательство. Проведём индукцию по числу рёбер Р. Если Р = 1, то либо это петля, и тогда В = 1, Г = 2, В – Р + Г = 2; либо это ребро, соединяющее 2 разные вершины, и тогда В = 2, Г = 1, В – Р + Г = 2. База индукции имеется. Предполагаем, что для графов с числом рёбер Р – 1 теорема верна. Добавим к такому графу одно ребро так, чтобы граф остался связным. Это можно сделать тремя способами.

1) Новое ребро – петля у одной из вершин. Добавляется 1 ребро и 1 грань, величина В – Р + Г не изменяется.

2) Новое ребро соединяет 2 разные вершины графа. Но граф плоский, и это ребро можно провести так, что оно не пересекает других рёбер, лежит в одной грани и делит её на две. Снова добавляется 1 ребро и 1 грань, величина В – Р + Г не изменяется.

3) Новое ребро инцидентно только одной из вершин графа. Тогда приходится добавлять новую вершину. Если она не лежит на ребре графа, то добавляется 1 ребро и 1 вершина, число граней не изменяется, величина В – Р + Г не изменяется. Если же новая вершина лежит на ребре, то это ребро делится на 2, грань делится на 2 грани. В этом случае добавляется 2 ребра, 1 грань и 1 вершина, величина В – Р + Г опять не изменяется.

27. Что такое правильная раскраска и хроматическое число графа?

Пусть G=(A,V) – неориентированный граф без петель, C c1,c2,,ck

– некоторое конечное множество – множество «цветов». Правильной раскраской графа называется такое отображение A-> C, что смежные вершины получают разные цвета. Наименьшее число k, при котором существует правильная раскраска, называется хроматическим числом графа: гамма(G)= k (стр.39)

28. Опишите алгоритм обхода графа «в глубину».

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

29. Опишите алгоритм обхода графа «в ширину».

Поиск «в ширину» Основная идея поиска «в ширину»: для данной вершины рассматриваются все смежные с ней, а затем происходит переход к другой вершине. Чтобы организовать такой процесс, нужен не стек, а очередь. Сначала заносится в очередь («проверяется») начальная вершина. Затем проверяются, заносятся в очередь смежные с ней. Когда все смежные проверены, вершина удаляется из очереди. Начинается проверка вершин, смежных с первой в очереди вершиной. Алгоритм заканчивает работу, когда все вершины проверены. Можно использовать алгоритм поиска «в ширину» для построения кратчайших маршрутов от начальной вершины до всех остальных. Такой маршрут можно зафиксировать сразу, как только вершина попадает в очередь, так как известна «предыдущая» (она первая в очереди), и кратчайший маршрут до неё уже построен.

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

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

Алгоритм Форда-Беллмана

Алгоритм Флоида

31. В каких случаях применяется алгоритм Форда?

Если рассматривать графы, у которых, возможно, есть рёбра с отрицательными ве-

сами, то для решения той же задачи приходится применять другие алгоритмы. Мы по-

знакомимся с алгоритмом Форда-Беллмана, позволяющим находить кратчайшие пути

от одной из вершин (источника) до всех остальных вершин в ориентированном взве-

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

32. В каких случаях применяется алгоритм Дейкстры?

Ставится задача: найти кратчайшие маршруты от одной из вершин (она на-

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

рассмотрим алгоритм Дейкстры, который можно применять, если нет рёбер с отрица-

тельными весами. При этом граф может быть как ориентированным, так и неориенти-

рованным.

33. В каких случаях применяется алгоритм Флойда?

Рассмотрим теперь задачу определения кратчайших маршрутов для всех пар вер-

шин графа. Задача решается для ориентированных взвешенных графов без циклов от-

рицательной длины.

34. Как решается задача о числе способов разместить n различных элементов в k различных ячеек?

Первую ячейку можно заполнить n способами, вторую, при заполненной первой, можно заполнить n–1 способами. Таким образом, существует п(п – 1) вариантов заполнения первых двух ячеек. Можно продолжать этот процесс до заполнения последней k–й ячейки. Эту ячейку при заполненных первых k – 1 ячейках можно заполнить

n–(k–1) (или n–k+1) способами. Таким образом, все k ячеек заполняются числом способов, равным: n(n-1)(n-2)...(n-k+2)(n-k+1)=n!/(n-k)!

Akn=n!/(n-k)!

35. Как решается задача о числе способов разместить k одинаковых элементов в n различных ячеек?

Выведем формулу для подсчета числа сочетаний. Пусть имеется множество Un и нужно образовать упорядоченное подмножество множества Un, содержащее k элементов (то есть образовать размещение). Делаем это так:

1) выделим какие-либо k элементов из n элементов множества Un Это, согласно сказанному выше, можно сделать Ckn способами;

2) упорядочим выделенные k элементов, что можно сделать Pk=k! способами. Всего можно получить Ckn*Pk вариантов (упорядоченных подмножеств), откуда следует: Akn =Ckn*Pk, то есть Ckn =Akn/Pk = n!/(k!(n-k)!)

 

 

36. Как определяются обычная и экспоненциальная производящие функции для числовой последовательности {an}?

Последовательности {an} - это формальный степенной ряд.

Производящая функция последовательности {an} - это формальный степенной ряд

(an*xn).

Зачастую производящая функция последовательности является рядом Тейлора некоторой аналитической функции.

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

Экспоненциальная производящая функция последовательности {an} - это формальный степенной ряд

(an*xn)/n!

37. Как строится производящая функция для последовательности k-сочетаний с повторениями элементов n-множества при различных ограничениях на число повторений?

23 страница

38. Как строится производящая функция для последовательности k-размещений с повторениями элементов n-множества при различных ограничениях на число повторений?

29 страница

39. Как строятся производящие функции для решения задачи о числе способов размещения элементов по ячейкам?

 

 

40. Что такое рекуррентная последовательность?

линейные однородные рекуррентные уравнения (ЛОРУ) с постоянными действительными коэффициентами:

 

 

стр 14. (*)

Здесь p1,p2…….pk – действительные числа, ai – i -й член некоторой последовательности

Число k называется порядком уравнения.

 

 

Если a0,a1,.....ak-1 заданы, то из соотношения (*) можно найти сначала k

a, затем a k+1 и так далее, можно определить любой член искомой последовательности. Итак,

уравнение (*) и значения a0,a1,.....ak-1 полностью определяют последовательность.

 

41. Какой вид имеет линейное реккурентное уравнение n-го порядка

 

 

42.Что такое общее и частное решения линейного однородного реккурентного уравнения 2-го порядка?

 

 

43.