Код Харари - Контрольная работа

бесплатно 0
4.5 19
Понятие графа в математической теории и информатике, виды и область применения графов. Код Харари, сущность идеи Ф. Харари, основателя теории графов. Нахождение кратчайшего пути во взвешенном графе, восстановление дерева по заданному коду Прюфера.


Аннотация к работе
Объекты представляются как вершины, или узлы графа, а связи - как дуги, или ребра.Идея Френка Харари - «упаковать» матрицу смежности в одно число. Меняя нумерацию вершин графа, так же получим другие двоичные строки (числа). Наибольшее из полученных чисел и есть код Харари, а нумерация вершин, давшая это число, называется канонической. Код Харари определяет граф однозначно. Для получения кода Харари необходимо найти каноническую нумерацию вершин данного графа, поэтому придется рассмотреть 6 нумераций вершин.A припишем индекс 0, а всем остальным вершинам индекс . В этот момент вершина B имеет индекс - это и есть наименьшая сумма весов. Построим этот путь, возвращаясь из вершины B в вершину Среди вершин, смежных с B обязательно найдется вершина C, для которой выполняется точное равенство: Возвращаемся в C и повторяем этот процесс. Вершину заносим в новый список, будущий код Прюфера, а вершину вычеркиваем и из списка и из дерева.

План
ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1. КОД ХАРАРИ

2. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1

Задача 2

Задача 3

Список литературы
1. Ф. Харари. ТЕОРИЯ ГРАФОВ. - М.: «МИР», 1973. - 301 с.

2. Н. Кристофидес. Теория графов. Алгоритмический подход. - М.: «МИР», 1978. - 429 с.

3. У. Татт. Теория графов. - М.: «МИР», 1988. - 424 с.

Размещено на .ru
Заказать написание новой работы



Дисциплины научных работ



Хотите, перезвоним вам?