10 билетПолный подграфПолный граф – граф, каждая вершина которого соединена ребром с остальными. Все вершины смежны.Плотность графа – максимальная мощность носителя полного подграфа1) Каждая пара вершин смежна.2) При добавлении хотя бы 1-ой вершины св-во 1 нарушается.Алгоритм порождения полных подграфов:1. Корню дерева сопоставляем исходный граф.2. Фиксируем вершину с наибольшей степенью и вершины её не окрестности, сопоставив их концу дуг, исходящей из корня дерева.3. Каждую вершину из п. 2 взвесить её окрестностью.4. Считать каждую вершину корнем дерева и рассматривать её окрестность.5. Выполнять п.2-5 пока вершина не будет взвешена Ø.11 билетПустой подграфПустой подграф – подграф, при добавлении к которому хотя бы одной вершины образуется хотя бы одно ребро.Окрестность вершины V0 (0(V0)) – подграф 0 ,V0>, носитель которого совпадает с окрестностью единичного радиуса, а сигнатуру образуют все рёбра, соединяющие эти вершины.Пустой подграф G-, не содержащий вершину V0Є V, содержит хотя бы одну вершину из её окрестности.^ Окрестность вершины – множество вершин смежные с нейАлгоритм порождения всех пустых подграфов.1. Сопоставить корню дерева исходный граф.2. фиксируем вершину с наименьшей степенью и вершин её окрестности, сопоставив концу каждой дуги, исходящей из корня дерева, вершину V0 и вершины её окрестности.3. Каждой из вершин из п.2 взвесить её неокрестностью.4. Считаем каждую из вершин корнем нового дерева.5 Выполнять п.2-5 пока вершина не будет взвешена Ø.Билет 8/9Положительная/Отрицательная устойчивость графа1. Условимся считать, что любая вершина графа покрывает сама себя и 2 смежные вершины покрывают друг друга, тогда минимальна мощность множества вершин, покрывающего все вершины графа называется числом внешней устойчивости графа β0(G)Если граф ориентированный, то β0+ (положительное число внешней устойчивости графа) – минимальная мощность множества вершин.V+={Vi+} такого, что {Vi+}U{Г Vi+}=VПри удалении хотя бы одной вершины из V+, данное соотношение не выполняется. Это число определяет минимальное количество вершин, из которых наблюдаются вершины графа.β0- - минимальная мощность множества вершин.V-={Vi-} такого, что {Vi-}U{Г-1 Vi}=Vβ0+(G) вычисляется как минимальная мощность покрытия столбцов строками.β0-(G) вычисляется как минимальная мощность покрытия строк столбцами в модифицированной матрице смежности Š(G) графа G.Модифицированной матрицей смежности называется дизъюнкция матрицы смежности и единичной диагональной матрицы.^ Билет 15. Алгоритм вычисления хроматического числа графа.Раскраска –разбиение носителя графа V, так чтобы любая пара вершин была бы не смежна. . Разбиением множества – мы разбиваем множество на подмножества так, чтоб при соединении давали само множество и не пересекались. Min число этих подмножеств называется хроматическим числом. h(G)=minj|{V}|j . Теорема: Если максимальная степень вершин графа G равна s(G), то хроматическое число этого графа не превышает величины s(G)+1; Алгоритм минимальной раскраски вершин графа G, т.е. алгоритм определения хроматического числа h(G).1 Выделяем множество вершинно пустых подграфов графа G(выделяем вершинно пустые подграфы графа G построением соответствующего дерева, фиксируя каждый раз в начале построения яруса вершину с минимальной степенью). 2 Строим двумерную таблицу, каждой строке которой взаимно однозначно сопоставляем пустой подграф, столбцу – вершину; в клетке (i,j) записываем 1, если J-ая вершина содержится в i-ом пустом подграфе, в противном случае клетку оставляем пустой.(Двумерная таблица, определяющая распределение вершин по пустым подграфам) 3 Определяем покрытие столбцов строками. Каждое покрытие порождает раскраску. Покрытие минимальной мощности определяет хроматическое число графа G. ^ Билет 6. Частично упорядоченное множество (посет). Понятие алгоритма.Важным классом многосортного множества является класс, элементами которого являются алгоритмы. Дадим интуитивное определение алгоритма. Алгоритмом называется двусортное множество (Мр,R2), где Мр- множество правил (процедур) решения задачи, обладающих следующими свойствами: Массовости – ивариантности относительно входной информации; Детерминированности – однозначности применения этих правил на каждом шагу; Результативности – получения после применения этих правил информации, являющейся результатом; Элементарности (прозрачности) – отсутствия необходимости дальнейшего уточнения правил. Символ R2- бинарное отношение в множестве Мр, R2М2р, (pi,pj)R, если после процедуры pi выполняется процедура pj. Способы задания алгоритма: Словесный (вербальный), графический (блок-схема), табличный, программный код, граф (в виде графа) , где V –действия; U-бинарные отношения. Вершина – команда(правило),Ребро- бинарное отношение. Если вершина является началом или концом одной дуги, правило называется арифметическим. Если правило является концом одной дуги, а началом нескольких дуг, то логическим. При этом происходит разветвление. Множество М с заданным в нем отношением упорядоченности называется упорядоченным этим отношением. Если любые два элемента mi и mj упорядоченного множества находятся в отношении упорядоченности mi^ Билет 13. Вложение графа в гиперкуб. Алгоритм.Большой практический интерес представляет проблема вложения графов в другие графы, имеющие специальные структурные свойства. Важным классом таких графов является класс n-мерных кубов. Они находят применение в теории кодирования при передаче данных и при проектировании автоматов. Обозначим n-мерный куб через Hn. Мощность его носителя равна 2n , мощность сигнатуры – n*2n-1. Множество вершин n-куба вместе с введенной таким образом метрикой, является метрическим пространством, которое назовем булевым пространством. Так как n-куб является двудольным графом, то в соответствии с теоремой Кёнига все его простые циклы четны, и поэтому любой граф, который содержит подграф, являющийся нечетным циклом, некубируем. Следовательно циклы нечетной длины и граф Кёнига К2,3 являются запрещенными фигурами вложения графа в булево пространство. Под запрещенной фигурой в данном случае понимаем критически невложимый граф, т.е. некубируемый граф, у которого все частичные графы кубируемые. ;называется изоморфным если существует такое взаимно однозначное соответствие между вершинами V и V’, что вершины Va и Vв соединены дугой (Va,Vв) в одном из графов в том и только в том случае когда соответствующие им вершины V’a и V’в соединены дугой (V’a,V’в) в другом графе.граф G изоморфен графу G’. Два графа гомеоморфные если они изоморфны с точностью степени два. Вложить граф в гиперкуб это значит установить изоморфизм между графом и гиперкубом. Гиперкубом – называется граф каждая вершина которого соответствует области пространства, и две вершины соединены ребром если они соответствуют соседним областям имеющих общую границу. Размерность пространства- размерность гиперкуба, n-значность логики.Алгоритм вложения графа в гиперкуб.1)устраняем запрещенные фигуры – структура в графе мешающая решению поставленной задачи-циклы нечетной длины, запрещенные фигуры при вложении графа в гиперкуб. Удаление запрещенных фигур осуществляется путем навешивания дополнительных вершин на соответствующие ребра. 2)Устанавливаем размерность а)maxS(V1); в) ]log2|V|[; из а и в выбираем мах- это и будет размерность гиперкуба; 3)Ярусно упорядочиваем граф начиная с вершины с мах степенью устанавливаем изоморфизм между графом и гиперкубом размерности n. При необходимости размерность куба может быть увеличена.^ Билет 14. Вложение графа в плоскостьРассмотрим топологические свойства графов. Топология исследует свойства графов, инвариантные относительно гомеоморфных преобразований. Эти свойства определяются топологическими инвариантами. Два графа гомеоморфны, если они изоморфны с точностью до вершин степени 2. Другими словами, два графа гомеоморфны, если они преобразуются до графов, изоморфных друг другу, заменой некоторых ребер цепями соответствующей длины. Род поверхности – это наибольшее число простых замкнутых кривых на поверхности, которые не разъединяют эту поверхность. Сфера и плоскость являются поверхностями нулевого рода, поскольку их разъединяет любая замкнутая прямая. Тор поверхность первого рода. Любая поверхность p-го рода эквивалентна сфере с p ручками. Граф называется планарным, если он изображается на плоскости так, что его ребра пересекаются только в вершинах. Теорема: Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного F5 или К3,3 или графов стягиваемых к F5 или к К3,3. Толщиной графа G называется наименьшее число планарных графов, объединение которых дает G. Толщина планарного графа равна 1. Нижняя оценка толщины t(G) графа определяется неравенством , где ] [ -целая часть, |V|=n, si- степень i –ой вершины. Чтобы определить, какие ребра необходимо удалить для преобразования графа в планарный, выделим все запрещенные фигуры и построим двумерную таблицу, каждая строка которой взаимно однозначно соответствует запрещенной фигуре Qi , a столбец – ребру Pi. тогда покрытие строк столбцами этой таблицы определит, какие ребра необходимо удалить, чтобы граф стал планарным. Минимальное покрытие будет соответствовать минимальному решению, так как удаление любого ребра выводит запрещенную фигуру из класса подграфов, гомеоморфных F5 или К3,3.Билет 4 Цикломатика. Порождение всех циклов в Графе.^ 1 Цикломатическая матрица С(G) – вторая матрица инциденций.Базис векторного пространства – это всякая система линейно зависимых векторов, порождающая данное пространство.^ Дерево – связный граф , не содержащий ни одного цикла. Остовный подграф графа – это подграф содержащий все вершины графа.Остов – остовный подграф, являющийся деревом.Хорды – ребра не вошедшие в остов.^ Лес – Это граф не содержащий циклов.Остовный лес – граф, каждая компонента которого является остовным деревом.Двудольный граф – это граф множество вершин которого разбивается на два пересекающихся подмножества V1 и V2 так, что каждое ребро в графе соединяет две вершины из разных подмножеств. G(V1,V2).Теорема Эйлера.Базисное кол-во циклов для заданного графа постоянно и равно цикломатическому числу , где к – количество компонент связности.2 Алгоритм порождения всех цикловПо теореме Эйлера найдем базисное кол-во цикловНайдем все множество циклов этого пространства. Построим цикломатическую матрицу(вторая матрица инциденций). Для построения матрицы выделяем базисные циклы относительно заданного остова.Билет 15Алгебра Буля.Закон идемпотентности дизъюнкции и конъюнкции. Закон коммуникативности Закон ассоциативности Закон дистрибутивности Закон двойного отрицания Закон Де – Моргана Закон склеивания Закон поглощения Закон Порецкого Законы определения действия константами 0 и 1 2.Дифф.графов.-В математ. Дифф.-есть нахождение производной. В основе лежит понятие предела.но в дискрет.матем. нет понятия предела. В дискрет.матем.производная показывает степень участия ребер или вершинграфа в каком-либо событии(например пустых подграфах).Событие(S)-исследуемый процесс,происходящий при выполнении определенных условий.каждое событие взаимно однозначно определяет матрицу (столбцу которой соответствует условие входящее в событие,строке-совокупность условий,при которых осуществляется событие.1,если j-е условие входит в I-ю совокупность условий,при которых событие истинноqij={ 0 в противном случаеЧастотной матрицей отношений F=[fij]n*n называется матрица ,каждой строке которой взаимно однозначно соответствует буква,и элемент fij равен числу слов, в которые входят буквы I и j,если iне=j,в противном случае(I=j)-числу слов,в которые входит буква i. При этом если I=j,то fi-собственная частота буквы,если же iне=j,то fij-взаимная частота букв I и j.Из определения следует,что матрица f симметрична относ. главной диагонали.Можно показать,что частотная матрица отношений F, характериз.модель,матрица инцидентности которой Q удовлетворяет соотношению qt*q=F.Производной от графа G по событию S называется неориентированный взвешенный граф (V,(U,P)),носитель которого совпадает с носителем модели,определяемой этим событием,и пара вершин(Vi,Vi) взвешена отношением частоты (fi-fij)+(fi-fij)их несовместного участия к частоте fij совместного участия в событии S G/s(Vi,Vj)=fi-2fij+fj / fij -значение производной на ребре(Vi,Vj)Причем 1. (Vi,Vj) не принадлежит U,если G/S(Vi,Vj)=бесконечность 2.(Vi,Vj) принадлежит U,если G/S(Vi,Vj)-конечная величина ,отличная от нуля. 3.Vi=Vj,если G/S(Vi,Vj)=0Нахождение dG/dS—Алгоритм .На примере участия вершин в пустых подграфах графа G1.Построить модель,опред.заданное событие и матрицу Q2.Находим Частотную матрицу отношений,соответствующую этой модели(F) F=Qt*Q3.Вычисляя по матрице F dG/dS на ребрах графа строим искомый граф dG/dS16,17. Минимизация переключательных функций в классе нормальных форм.Важной задачей является минимизация количества повторений предметных переменных в аналитическом задании переключательных функций.Сложностью L(f) является аналитическое выражение переключательной функции f(x1,x2,…….,xn) называется количество включений предметных переменных в это выражение.Рассмотрим минимизацию булевых функций в классе ДНФ.Зададим булеву функцию f(x1,x2,…….,xn) с помощью гиперкуба, каждой вершине которого взаимно однозначно соответствует двоичный набор (1,2,…. n); вершины упорядочены по ярусам (в I-ой ярус входят C(n,i) вершин, которым соответствуют двоичные наборы, содержащие I -единиц); вершины соединены ребром, если соответствующие им двоичные наборы отличаются в одном и только одном разряде.Вершины, в которых f(x1,x2,…….,xn) =1 и которые образуют гиперкуб, порождают единичный интервал этой функции. Единичный интервал Ia булевой функции f называется максимальным, если не найдется единичный интервал Ib , строго включающий Ia.Конъюнкция, соответствующих максимальному единичному интервалу функции f , называется простой импликантной этой функции.Дизъюнкция всех простых импликант булевой функции называется сокращенной ДНФ этой функции.Переход от совершенной ДНФ к сокращенной однозначен и осуществляется с помощью по парного сравнения конститует соседних ярусов (номера которых отличаться на единицу).Согласно теореме Стоуна тупиковая ДНФ функции f(x1,x2,…….,xn) изоморфна тупиковой НФК множества M(M1, M2,……Mn). Следовательно, алгоритм построения минимальной ДНФ изоморфен алгоритм вычисления минимальной НФК.1. Понятие графа и способы его задания Квадрат множества М – декартово произведение равных между собой множеств М2= =М*М. Бинарное отношение Т в множестве М – подмножество его квадрата ТСМ2miиmjнаходятся в бинарном отношении Т, если (mi; mj) Є Т. Совокупность множества М с данными в нём бинарным отношением Т Є М2 – Граф G. G=, М- Носитель графа (множество вершин), Т- сигнатура графа (множество дуг (рёбер)). Способы задания: 1)перечисление элементов множества 2)Матрица смежности 3)графически 4)с помощью фактор - множества (множество сечений взятых для всех элементов множества). 5)матрица инциденций. 6) Матрица весов дуг и вершин (для графа без петель).Билет 3Связность графа. Алгоритм определения связности графаЦепь, цикл, матрицы смежности.Граф называется связным, если пары его вершин соединены цепью. Максимальный по включению вершин связный подграф графа - его компонента связности. Если граф содержит более одной компоненты связности - граф несвязный. Условие связности: D (G) =ΣM(G)i=1[S]I Алгоритм определения связности графа. Возводим матрицу S В n-ую степень Здесь в матрице SnSIJ- пути из Viв Vj длиной n. 2. Если в матрице d’ нет нулевых элементов граф является связным (к=1), d(G)- диаметр графа - кратчайший путь между вершинами. 3.связность графа (X(G)) наименьшее число вершин, удаление которых делает граф несвязным. Если X(G)=n, то граф называется n-связным. Рёберная связность (M(G))- наименьшее количество рёбер, удаление которых делает граф несвязным.5.Разрез графа – множество рёбер, при удалении которых связанный граф перестает быть связным, а при добавлении в это множество хотя одного ребра, не вошедшего в это множество граф, становится связным. Х - поциклический рост.- число ребер в остовном лесе графа: Х(G)=|V|- k Дерево - связный граф, не содержащий циклов. Остовной подграф - подграф, содержащий все вершины графа. Остов - остовной подграф являющийся деревом. Остовной лес- граф, каждая компонента которого связности которого является остовным деревом. Остовной лес V+ V V -Есть исток сток Алгоритм нахождения всех разрезов.X(C) =6-1=5Находим базисные разрезы относительно остова. Остов Хорды a b c d e f g h i R1 1 0 0 0 0 1 0 0 0 R2 0 1 0 0 0 1 1 0 0 R3 0 0 1 0 0 1 1 1 0 R4 0 0 0 1 0 1 1 1 1 R5 0 0 0 0 1 1 1 0 1 R6 R7 R8 R9 R10 Всего 2х-х-1 сложений по модулю 2 Порождение остальных графов 25-5-1=26. На практике: Максимальный поток через сеть- минимальная пропускная способность её разреза. Сеть - ориентированный граф, в котором выделено 2 множества полюсных вершин V+и V – таких, что в каждую вершину V- входят только рёбра, V+ только выходят