Код Харари
Понятие графа в математической теории и информатике, виды и область применения графов. Код Харари, сущность идеи Ф. Харари, основателя теории графов. Нахождение кратчайшего пути во взвешенном графе, восстановление дерева по заданному коду Прюфера.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 24.11.2014 |
| Размер файла | 253,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Кафедра «Высшая математика»
КОД ХАРАРИ
КОНТРОЛЬНАЯ РАБОТА
по дискретной математике
2011
ОГЛАВЛЕНИЕ
- ВВЕДЕНИЕ
- 1. КОД ХАРАРИ
- 2. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
- Задача 1
- Задача 2
- Задача 3
ВВЕДЕНИЕ
В математической теории графов и информатике граф - это совокупность непустого множества вершин и множества пар вершин.
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Ниже будет рассмотрен один из способов представления графов в памяти ЭВМ - с помощью кода Харари.
граф математический харари код
1. КОД ХАРАРИ
Фрэнк Харари (англ. Frank Harary) (11 марта 1921 - 4 января 2005) - американский математик, специализировавшийся в теории графов. Является признанным основателем современной теории графов.
Идея Френка Харари - «упаковать» матрицу смежности в одно число.
Пусть дан неориентированный граф. Мы уже знаем, что его матрица смежности A симметрична относительно главной диагонали, и достаточно хранить только ее верхний треугольник. Расположим его в виде двоичной строки (слева направо или сверху вниз).
Меняя нумерацию вершин графа, так же получим другие двоичные строки (числа).
Сравним их между собой именно как числа (по первому биту). Наибольшее из полученных чисел и есть код Харари, а нумерация вершин, давшая это число, называется канонической.
Код Харари определяет граф однозначно.
При общении между людьми код Харари принято переводить в 10-е число.
Пример. Найти код Харари графа:
Решение.
Для получения кода Харари необходимо найти каноническую нумерацию вершин данного графа, поэтому придется рассмотреть 6 нумераций вершин.
1-ая нумерация.
Восстановим матрицу для графа с полученной нумерацией. Матрица A будет симметричной.
Верхний треугольник
Попробуем не «безумно» менять нумерацию вершин, а стремиться получить наибольшую из них, то есть сразу каноническую.
Вершину с петлей нумеруем 1-ой, а соединенную с ней 2-ой.
Восстановим матрицу для графа с полученной нумерацией.
Верхний треугольник
Очевидно, увеличить полученное число нельзя, значит, полученная нумерация графа является канонической. Переведя двоичное число в 10-ю систему, получим код Харари.
Видимо, существует алгоритм, сразу нумерующий вершины графа каноническим образом, учитывая петли и число соединений (степени вершин).
Максимальным код Харари будет в том случае, когда в графе присутствует наибольшее количество возможных связей вида 1-2, 1-3, 1-4, 1-5 …, 2-3, 2-4 … (где цифры - нумерация вершин графа), то есть если индекс -вершины минимален, а количество связей с другими вершинами (имеющими индекс , где - натуральное число, причём ) максимально, то и код Харари будет максимален.
Заметим, что не всякое десятичное число является кодом Харари какого-либо графа. Дело в том, что проделав все эти действия в обратном порядке, мы получим граф с нумерацией вершин, которая вовсе не обязана быть канонической.
1. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1
Найти кратчайший путь из A в B во взвешенном графе.
Воспользуемся алгоритмом поиска пути во взвешенном графе.
Будем постепенно приписывать всем вершинам графа числовые индексы.
Шаг 1. Вершине A припишем индекс 0, а всем остальным вершинам индекс .
Шаг 2. Последовательно перебираем все пары смежных вершин x и y.
Каждый раз проверяем неравенство:
Если оно выполняется, то уменьшаем индекс , заменив его на .
Шаг 3. Процесс останавливаем, когда не один индекс нельзя уменьшить. В этот момент вершина B имеет индекс - это и есть наименьшая сумма весов. Построим этот путь, возвращаясь из вершины B в вершину A.
Шаг 4. Среди вершин, смежных с B обязательно найдется вершина C, для которой выполняется точное равенство:
Возвращаемся в C и повторяем этот процесс. Так как при этом индексы все время уменьшаются, то через несколько шагов мы придем в вершину индекса «0», то есть в A.
Один или несколько путей построено.
Проделав вышеуказанные действия, получим следующий граф:
Пути в данном графе:
1.
2.
3.
Задача 2
Восстановить дерево по заданному коду Прюфера .
Воспользуемся алгоритмом, чтобы восстановить дерево по коду Прюфера.
Пусть имеется дерево с -пронумерованными вершинами. В списке всех вершин 1 2 3… слева направо ищем первую висячую вершину. Пусть это . Ищем единственную вершину , с которой смежна .
Вершину заносим в новый список, будущий код Прюфера, а вершину вычеркиваем и из списка и из дерева. Этот процесс повторяем раза. В результате получаем новый список вида - это и есть код Прюфера.
Заметим, что в процессе построения дерево все время уменьшается и возникают новые висячие вершины.
Код Прюфера равен . Восстановим дерево по заданному коду.
Количество вершин дерева равно .
Восстановленное дерево будет иметь вид:
Задача 3
Восстановить граф, считая, что число 726 - код Харари. Проверить, является ли нумерация вершин полученного графа канонической, то есть является ли число 726 действительно кодом Харари.
Переведем код из десятичного представления в двоичное представление:
Восстановим матрицу по двоичному коду Харари:
Восстановим граф по матрице:
Предположим, что данная нумерация не является канонической. Следовательно, будем искать каноническую нумерацию. Поменяем в нумерации вершин 1 и 4, 2 и 3. Получим следующий граф:
Построим матрицу для полученного графа. Матрица будет иметь вид:
Сравним начальный код с полученным:
Очевидно, полученный код больше исходного кода. Следовательно, исходная нумерация графа не является канонической, а число 726 не является кодом Харари.
Полученная нумерация вершин является канонической для данного графа, следовательно, число 980 является кодом Харари.
СПИСОК ЛИТЕРАТУРЫ
1. Ф. Харари. ТЕОРИЯ ГРАФОВ. - М.: «МИР», 1973. - 301 с.
2. Н. Кристофидес. Теория графов. Алгоритмический подход. - М.: «МИР», 1978. - 429 с.
3. У. Татт. Теория графов. - М.: «МИР», 1988. - 424 с.
Размещено на Allbest.ru
...Подобные документы
История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Понятие "граф". Отношения между разнородными элементами. Матричное представление графов. Операции над графами. Маршруты, цепи, циклы. Метрические характеристики графа. Приложение теории графов в различных областях науки и техники. Листинг программы.
курсовая работа [725,8 K], добавлен 15.12.2008Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Сущность и основные понятия теории графов, примеры и сферы ее использования. Формирование следствий из данных теорий и примеры их приложений. Методы разрешения задачи о кратчайшем пути, о нахождении максимального потока. Графическое изображение задачи.
курсовая работа [577,1 K], добавлен 14.11.2009Типы бинарных отношений. Изображение графов в виде схемы. Цикл в графе, совпадение его начальной и конечной вершины. Понятие достижимости в теории графов, их математические свойства. Частично упорядоченное множество как один из типов бинарного отношения.
контрольная работа [116,5 K], добавлен 04.09.2010Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013Элементы теории графов. Центры и периферийные вершины графов, их радиусы и диаметры. Максимальный поток транспортировки груза и поток минимальной стоимости. Пропускная способность пути. Анализ сетей Петри, их описание аналитическим и матричным способами.
задача [1,3 M], добавлен 28.08.2010Основополагающие понятия теории графов и теории групп. Определение эквивалентности, порождаемой группой подстановок, и доказательство леммы Бернсайда о числе классов такой эквивалентности. Сущность перечня конфигурации, доказательство теоремы Пойа.
курсовая работа [682,9 K], добавлен 20.05.2013Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.
курсовая работа [649,2 K], добавлен 18.01.2014
