Comments 8
Спасибо за статью.
Скажите, а нельзя ли как нибудь упорядочит графы, что бы их можно было пронумеровать (перебирать в цикле). Я как бы понимаю, что есть канторова нумерация, и вроде бы даже понял как нумеровать многоугольники, но не могу догадатся как нумеровать графы.
Скажите, а нельзя ли как нибудь упорядочит графы, что бы их можно было пронумеровать (перебирать в цикле). Я как бы понимаю, что есть канторова нумерация, и вроде бы даже понял как нумеровать многоугольники, но не могу догадатся как нумеровать графы.
Вы про кодирование простых графов числом? Для деревьев есть код Прюфера. Для произвольного графа вроде бы нет универсального кода. Но возможно, вы что-то другое имеете в виду, — я не очень понял проблему.
Задача формулируется так: нужно перебрать в цикле все графы содержащие, допустим, от двух до 20 вершин (рассматриваются графы без петель и изолированных вершин).
В принципе, такой перебор не составляет никакого труда. Но очень любопытно, как организовать такой перебор без вложенных циклов. Единственный способ добиться этого заключается в создании какого-то правила, которое может однозначно сопоставлять каждому графу единственное натуральное число. Без этого правила приходится пользоваться вложенными циклами. Но еще один бонус от такого правила — это понижение размерности, т.е. возможность отображать отображать графы в виде точек на координатной плоскости и воспринимать графы как многообразие.
В принципе, такой перебор не составляет никакого труда. Но очень любопытно, как организовать такой перебор без вложенных циклов. Единственный способ добиться этого заключается в создании какого-то правила, которое может однозначно сопоставлять каждому графу единственное натуральное число. Без этого правила приходится пользоваться вложенными циклами. Но еще один бонус от такого правила — это понижение размерности, т.е. возможность отображать отображать графы в виде точек на координатной плоскости и воспринимать графы как многообразие.
Уже понятнее, но все равно не конца. Возможный изоморфизм графов нас волнует в этом переборе или нет? То есть если попадутся два графа топологически эквивалентных — это допустимо или нет?
Про бонус тоже не понял. Понижение размерности чего? И что за «координатная плоскость», на которой можно графы отображать? Графу сколько чисел соответствует — одно, два или сколько?
Про бонус тоже не понял. Понижение размерности чего? И что за «координатная плоскость», на которой можно графы отображать? Графу сколько чисел соответствует — одно, два или сколько?
Про понижение размерности согласен, звучит странно. Даже не знаю, как корректно сформулировать, поэтому зайду издалека. Рассмотрим треугольники с целочисленными (рациональными) сторонами. Для них можно придумать простое правило которое сопоставляет каждому треугольнику единственную целочисленную точку на двумерной плоскости. Кажется это называется отображением, т.е. между любым целочисленным треугольником и любой целочисленной точкой на плоскости есть однозначное и единственное соответствие. Далее мы можем использовать это отображение для того что бы решать какие-нибудь геометрические задачи о треугольниках в целочисленном виде. Например, вот на этой картинке изображены треугольники с одной целой медианой:
Это позволяет заметить, что решения размещаются на гиперболах, парабалах и прямых. Так же это позволяет заметить важное ограничение и то что все треугольники не попавшие на график подобны, т.е. на порядки сократить перебор кандидатов на решение.
Словосочетание «понижение размерности» конечно же некорректно. Но суть в том, что задача от трех переменных превратилась в задачу от двух переменных. А далее с помощью Канторовой нумерации можно перейти к единственному числу, т.е. сопоставить каждой паре чисел (координаты целочисленной точки на плоскости) единтсвенное натуральное число.
Как правильно задать вопрос о нумерации графов… не знаю. Поэтому нарисую :) Допустим у нас есть неориентированные графы, топологически эквивалентные графы считаются одинаковыми:
Можно ли придумать какое-то правило или последовательность каких-то правил, что бы осуществить отображение множества всех таких графов в множество натуральных чисел, т.е. что бы сопоставить каждому графу некоторое натуральное число.
Смысл затеи заключается в ускорении решения задач комбинаторной оптимизации, благодаря такому «понижению размерности». В качестве аналогии можно рассмотреть метод PCA (метод главных компонент), но без потери информации.
Это позволяет заметить, что решения размещаются на гиперболах, парабалах и прямых. Так же это позволяет заметить важное ограничение и то что все треугольники не попавшие на график подобны, т.е. на порядки сократить перебор кандидатов на решение.
Словосочетание «понижение размерности» конечно же некорректно. Но суть в том, что задача от трех переменных превратилась в задачу от двух переменных. А далее с помощью Канторовой нумерации можно перейти к единственному числу, т.е. сопоставить каждой паре чисел (координаты целочисленной точки на плоскости) единтсвенное натуральное число.
Как правильно задать вопрос о нумерации графов… не знаю. Поэтому нарисую :) Допустим у нас есть неориентированные графы, топологически эквивалентные графы считаются одинаковыми:
Можно ли придумать какое-то правило или последовательность каких-то правил, что бы осуществить отображение множества всех таких графов в множество натуральных чисел, т.е. что бы сопоставить каждому графу некоторое натуральное число.
Смысл затеи заключается в ускорении решения задач комбинаторной оптимизации, благодаря такому «понижению размерности». В качестве аналогии можно рассмотреть метод PCA (метод главных компонент), но без потери информации.
Поскольку треугольники отображаются на плоскость, то каждому соответствует все-таки два числа, а не одно.
В целом же задачи перечисления разного рода объектов являются предметом изучения перечислительной комбинаторики. Там много интересных результатов, но насколько мне известно, задача перечисления графов в том виде, в котором вы ее описали, — не решена.
В целом же задачи перечисления разного рода объектов являются предметом изучения перечислительной комбинаторики. Там много интересных результатов, но насколько мне известно, задача перечисления графов в том виде, в котором вы ее описали, — не решена.
—
Sign up to leave a comment.
Экспресс-анализ метрических параметров графов