Понятие графа в математической теории и информатике, виды и область применения графов. Код Харари, сущность идеи Ф. Харари, основателя теории графов. Нахождение кратчайшего пути во взвешенном графе, восстановление дерева по заданному коду Прюфера.
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или ребра.Идея Френка Харари - «упаковать» матрицу смежности в одно число. Меняя нумерацию вершин графа, так же получим другие двоичные строки (числа). Наибольшее из полученных чисел и есть код Харари, а нумерация вершин, давшая это число, называется канонической. Код Харари определяет граф однозначно. Для получения кода Харари необходимо найти каноническую нумерацию вершин данного графа, поэтому придется рассмотреть 6 нумераций вершин.A припишем индекс 0, а всем остальным вершинам индекс . В этот момент вершина B имеет индекс - это и есть наименьшая сумма весов. Построим этот путь, возвращаясь из вершины B в вершину Среди вершин, смежных с B обязательно найдется вершина C, для которой выполняется точное равенство: Возвращаемся в C и повторяем этот процесс. Вершину заносим в новый список, будущий код Прюфера, а вершину вычеркиваем и из списка и из дерева.
План
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. КОД ХАРАРИ
2. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Задача 1
Задача 2
Задача 3
Список литературы
1. Ф. Харари. ТЕОРИЯ ГРАФОВ. - М.: «МИР», 1973. - 301 с.
2. Н. Кристофидес. Теория графов. Алгоритмический подход. - М.: «МИР», 1978. - 429 с.
3. У. Татт. Теория графов. - М.: «МИР», 1988. - 424 с.
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
