|
|
Множествами объединение, пересечение, разность и симметрическая разность, дополнение. Свойства операций и принцип двойственности правила
Кодирование деревьев. Метод Пруфера. Построение дерева по его коду.
Пусть имеем граф с пронумерованными вершинами Артур Кели поставил задачу: сколько сущ-ет деревьев построенных на N помеченных вершинах в смысле изменения вариантов соединения вершин. И выяснили N=n n-2
Метод Пруфера:
На каждом шаге удаляется висячая вершина с наименьшим номером и в кодовую последовательность заносится номер смежной ей вершины, после чего ребро удаляется.
Повторяется шаг 1 до тех пор пока не останется в графе 1 ребро с 2-мя вершинами одна из которых на последнем шаге замыкает кодовую последовательность поэтому длина кода равна n-2 две не вошедшие в кодовую последовательность вершины не нарушат условия однозначности восстановления(декодирования) дерева по его коду т.к. две недостающие вершины необходимо соединить ребром. Обратный пример (декодирование):
Подсчитываем длину кодовой последовательности и определяем число вершин N добавляет к нему 2
Строим новое множество к=К0=(…) Которое с учетом ранжирования по возрастанию, помещаются отсутствующие номера вершин в коде.
Удаляем одновременно 1 элемент из кода и 1 элемент из W (он является min) затем на подготовленном поле листа соединяем вычеркнутые номера из K и W подготавливаем новое множество К и новое множество W для следующего шага: 1 мн-во уменьшается на удаленный первый элемент во втором множестве W также удаляется первый элемент и возможно добавление в него удаленного первого элемента из К в том лишь случае если удаляемый 1 элемент из мн-ва К в нем не повторялся Заносится этот элемент в W с учетом упорядочения по возрастанию.
Шаг 3 повторяется до того пока кодовая последовательность К не будет пустой. Оставшиеся элементы W соединяются ребром на графе.
|
Разрезы. Гипотеза 4-х красок. Хроматическое число графа. Определение: разрезом наз-ся минимальное разделяющее мн-во т.е. такое разделяющее мн-во у которого нет собственного разделяющего подмножества.
Как находить разрезы: разрез (совокупность удаляемых ребер) можно получить переходя от одной точки к какой либо грани исходного графа к другой точке другой грани этого же графа и проходя через все грани исходного графа к другой точке другой грани этого же графа включая и внешнюю грань при этом эта линия маршрута (обхода) пометит те ребра которые и входят в разрез. Маршрут обхода по граням должен быть замкнут т.е. он должен возвращаться в исходную точку 1 выбранной грани. Такие замкнутые маршруты будут представлять собой простые цифры двойственного графа.
Сколько простых циклов в двойственном графе столько и вариантов разреза исходного графа.
Гипотеза 4-х красок: на географических картах территории стран раскрашивают так чтобы соседние страны имели различные цвета, какое минимальное число красок будет достаточно для такого условия раскрашивания карт, если даже число стран будет постоянно увеличиваться и границы могут приобретать произвольную конфигурацию. Пока не доказано что достаточно 4 красок однако перебором всех вариантов даже для очень большого кол-ва стран которые в графе представлены вершинами имеющими в том случае соединения меж собой если соответствующие страны имеют общую границу.
Хроматическое число графа на N вершинах
= N В полном графе каждая вершина соединена между собой.
Теорема: если через Р обозначить степень вершины то этот граф можно раскрасить (Р+1) красками (Р не обязательно совпадает с хроматическим числом)
|
Понятие орграфа. Матрица смежности. Изоморфизм. Смешанный граф. Определение:
граф содержащий только дуги ориентированные соединения в виде стрелок наз-ся орграфом Определение: граф в котором наряду с ребрами имеются в наличии и дуги хотяб наз-ся смешанным графом его можно изоморфно представить в виде орграфа если все ребра заменить на пары встречных дуг.
Определение: множество � = {(�, �)/
�, � ∈ �} упорядочен пар вершин наз-ся квадратом множества вершин. V*V=V 2 Аналитически орграф так же как и неориентированный граф задается G={V,F}
Замечание: Если нет кратных дуг то FC�2
=Z Если нет к любой дуге встречной дуги т.е. орграф не может быть сведен к смешанному графу тогда множество F является собственным подмноеством. Два графа изоморфны если изоморфны их основания полученные путем замены всех дуг ребрами и совпадают направления всех соответствующих друг другу дуг. V={1,2,3,4,5} F={(1,2),(1,3),(2,3),(2,4),(3,4),(4,2),(4,5),(4, 4)}
|
Степень вершины орграфа. Маршруты, цепи, циклы в орграфах.
Ответ: Степень в орграфах определяется с учетом степени входа и степени выхода. Маршруты, цепи, циклы в орграфах определяются так же, как и в случаях неориентированных графов, но с учетом того, что движение возможно лишь в направлении стрелок.
|
Связность орграфа. Эйлеровы цепи и циклы в орграфе. Полный орграф. Ответ: Орграф на n вершинах называется сильно связанным, сели существует простая ориентированная цепь, соединяющая любые две вершины.
Орграф называется слабо связанным, если его основанием является связанный граф.
Орграф называется несвязанным, если число компонентов его основания превышает единицу.
Ориентированная замкнутая цепь называется эйлеровой, если она содержит все дуги графа (эйлеров цикл).
Орграф называется полным, если его основание есть полный граф.
|
О теории трансверсалей. Теорема Холла о системе различных представителей.
Метод нахождения всех трансверсалей (метод Петрика).
Ответ: Пусть М1 , М2 ,…, Мm – непустые подмножества некоторого множества Е. Составим из них семейство L, содержащее m подмножеств: L = (М1, М2 , …, Мm). Из каждого подмножества, входящего в семейство L, выберем по одному элементу так, чтобы
Получилось упорядоченное множество W, содержащее m различных элементов называется трансверсалью семейства L. Теорема Холла о системе различных представителей: Пусть G=(V1,V2,E) – двудольный граф, тогда граф G имеет совершенное паросочетание ⇔ ∀A ⊆ V1: (|A| ≤ |S(A)|)
Метод Петрика:
Упростить таблицу простых импликант, исключив необходимые импликанты и соответствующие им термы.
Обозначить строки упрощенной таблицы: P1, P2 и т. д.
Сформировать логическую функцию P, которая истинна когда покрыты все столбцы. P состоит из КНФ, в которой каждый конъюнкт имеет форму (Pi0+Pi1+…+PiN), где каждая переменная Pij представляет собой строку, покрывающую столбец i.
Упростить P до минимальной ДНФ умножением и применением X+XY=X, XX=X и X+X=X.
Каждый дизъюнкт в результате представляет решение, то есть набор строк, покрывающих все минтермы в таблице простых импликант.
Далее для каждого решения, найденного в шаге 5 необходимо подсчитать количество литералов в каждой простой импликанте.
|
Нахождение максимальной пропускной способности транспортной сети.
Ответ: Транспортной сетью называется орграф, в котором имеются точно одна вершина со степенью входа, равной нулю, точно одна вершина со степенью выхода, равной нулю, и в котором каждой дуге поставлено в соответствие некоторое число, называемое пропускной способностью дуги.
|
Орграфы и бинарные отношения.
Диаграммы Хассе. Ответ: Бинарные отношения:
Симметричные отношения
Рефлексивные отношения
Транзитивные отношения
Антисимметричные отношнения, Диаграммой Хассе называется ориентированный граф (V,A) с V = X и A =
{(u,v): u |
|
|
Выбрать терм (или термы), содержащие минимальное количество литералов и записать результат.
|
|
|
Гамильтоновы графы. Задача о коммивояжере. Ответ: Граф, содержащий гамильтонову линию, называется гамильтоновым графом.
Задача о коммивояжере: Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в неизвестном порядке города 2,3,4..n и вернуться в первый город.
Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
|
|
|
| |
|
|
Скачать 134.15 Kb.