1. Код Хаффмана не обладает префиксным свойством, а значит, не подходит для моих задач.
2. Этот алгоритм много где используется, но не используется алфавит на 300 млн образов. Проблема не в реализации, а в её скорости.
3. Адаптивный алгоритм это другое. Он используется, если неизвестна частота символов в алфавите.
Если верить Глебу, который эту задачку задал, то количество вершин должно быть чётным.
Разбить на пары смежных — это значит, что выделить пары вершин так, чтобы они были соединены ребром, но при этом входили только в одну смежную пару.
Такое я тоже предлагал. Мне сказали, что всё это не то. На вопросы чем это не граф, они как-то потерялись и сказали искать простой граф без петель и кратных рёбер. P.S. Но формулировка задачи приведена дословно.
И да, я почитал тексты по вашей ссылке. Определение графа мне очень понравилось. Я даже процитирую: «Графом без петель и кратных ребер называется набор точек, некоторые пары которых соединены ли-
ниями, причем одна пара вершин не может быть соединена более чем одной линией. Точки называются
вершинами графа, а линии – ребрами. Линии могут не быть отрезками. Им разрешается пересекаться, но
точки пересечения ”не считаются”, то есть не являются вершинами.» Это очень строгое и точное определение. Именно такой и должна быть матчасть.
«Выдуманное вами «направление» не подходит под понятие ребро» — в ориентированном графе нет рёбер? Не верю. И не надо отсылать меня к матчасти, я её весьма неплохо знаю.
Б.Н. Иванов. «Дискретная математика». Учебное пособие. стр. 110-112. Мы можем сколько угодно писать друг-другу определения. Более того, мы можем задать направление петле. Но даже это не будет решением. Давайте лучше вместе подумаем, как решить эту задачу?
Некоторые говорят, что степень вершин в моём графе 6. Я с этим не согласен, так как вот определения:
1. Если вершины x,y соединены ребром u, то говорят, что вершины смежные, а ребро u инцидентно вершинам x,y.
2. Степенью вершины графа называют количество рёбер, инцидентных данной вершине.
Если же вы считаете, что петля входит дважды, достаточно каждой петле задать направление.
