Комментарии 15
Честно говоря, не впечатляет… Если я правильно понял, то мы просто пошагово разворачиваем граф в дерево с дублированием вершин. В текстовой форме такая скобочная форма будет неудобна, т.к. только мешает «обзору» структуры графа. Применение в программировании тоже достаточно сомнительно. Разве что действительно такое представление действительно помогает упрощать доказательства и формулировки в теории графов.
И что насчёт случая если граф содержит несколько компонент связности? Ведь придётся для каждой компоненты делать свою запись, сначала найдя эти самые компоненты.
И что насчёт случая если граф содержит несколько компонент связности? Ведь придётся для каждой компоненты делать свою запись, сначала найдя эти самые компоненты.
А компактность хранения информации? Если необходимо хранить достаточно большое количество простых графов, такая форма может быть удобна.
О какой компактности речь, если здесь вершины дублируются, причём зачастую не единожды? И удобна для чего? Если для поиска минимального расстояния от «нулевой» вершины до любой другой, то безусловно, а вот для хранения произвольного графа в сериализованном виде, то уже довольно сомнительно.
Собеседники правы — это далеко не самый компактный способ записи. Но и не в этом его основная задача.
Не соглашусь по некоторым моментам. Такая форма записи дает большее представление о коммуникативных свойств, описываемого графа нежели матричная форма записи. Легко определить такие показатели, как диаметр, обхват, эксцентриситет. Операции на графом в скобочной форме, например, удаление вершин, стягивание ребер, очень просты в реализации. Так удаление вершины есть изъятие ее и порождаемых ею (т.е. находящихся внутри скобок при ней) вершин из образа. Это позволяет производить реконфигурации структуры формальным путем, не прибегая к графическому представлению.
А по поводу компонент связности вы верно подметили. Но то лишь частный случай, не дающий всех преимуществ.
А по поводу компонент связности вы верно подметили. Но то лишь частный случай, не дающий всех преимуществ.
Вполне возможно. Просто при работе с графами мне ещё не приходилось на глазок оценивать данные параметры, не в последнюю очередь потому что обычно имеешь дело с достаточно большими графами, а если нужно набросать алгоритм на графах, то удобнее графическая форма.
Поэтому и написал, что данная форма скорее будет полезна в математике, чем в программировании.
Поэтому и написал, что данная форма скорее будет полезна в математике, чем в программировании.
Вы забыли ещё про структурную запись, в которой граф записывается в виде: узел + его соседние узлы (и так n строк по одной на каждый узел). И, на мой взгляд, оно более наглядное, чем скобочное.
А удобно ли применять структурную запись в задачах синтеза графа с уже известными свойствам?
Я к тому, что скобочная форма записи удобна скорее не для хранения информации о графе, а для осуществления над ним преобразований или анализа.
Я к тому, что скобочная форма записи удобна скорее не для хранения информации о графе, а для осуществления над ним преобразований или анализа.
Вы говорите об удобстве. А можете привести конкретный пример? Я имею в виду не в общих словах, как это сказано в статье, а реальный пример. Или достойную реализацию данной структуры данных на каком-нибудь языке (C/C++, Java...) в виде класса, включающего различные методы, позволяющие анализировать или преобразовывать граф, к примеру? Просто по всем публикациям Мелентьева искать — дело не благодарное, сначала хочется понять на наглядном примере, надо ли это вообще…
Они изобрели Common Lisp?
По моему похожую структуру умеет выдавать любой приличный XML сериализатор…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Скобочная форма описания графов