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