Сопоставление графиков

Сопоставление графов — это проблема поиска сходства между графами . ^[1]

Графы обычно используются для кодирования структурной информации во многих областях, включая компьютерное зрение и распознавание образов , а сопоставление графов является важным инструментом в этих областях. ^[2] В этих областях обычно предполагается, что сравнение проводится между графом данных и графом модели .

Случай точного сопоставления графов известен как проблема изоморфизма графов . ^[1] Задача точного сопоставления графа части другого графа называется проблемой изоморфизма подграфов .

Неточное сопоставление графов относится к проблемам сопоставления, когда точное сопоставление невозможно, например, когда количество вершин в двух графах различно. В этом случае необходимо найти наилучшее возможное совпадение. Например, в приложениях распознавания изображений результаты сегментации изображений при обработке изображений обычно создают графы данных с числом вершин, намного большим, чем в модельных графах, с которыми, как ожидается, будут сопоставляться данные. В случае атрибутированных графов , даже если число вершин и ребер одинаково, сопоставление все равно может быть неточным. ^[1]

Две категории методов поиска — это методы, основанные на выявлении возможных и невозможных пар вершин между двумя графами, и методы, которые формулируют сопоставление графов как задачу оптимизации . ^[3] Расстояние редактирования графа является одной из мер сходства, предлагаемых для сопоставления графов. ^[4]^[5] Класс алгоритмов называется устойчивым к ошибкам сопоставлением графов. ^[5]

См. также

Ссылки

^ Jump up to: Перейти обратно: ^а ^б ^с Эндика Бенгоэчеа, «Неточное сопоставление графов с использованием оценки алгоритмов распределения». Архивировано 11 января 2017 г. в Wayback Machine , Ph. D., 2002, Глава 2: Проблема сопоставления графов. Архивировано 16 мая 2017 г. на Wayback Machine (получено 28 июня 2017 г.).
^ Эндика Бенгоэчеа, доктор философии, реферат заархивирован 11 января 2017 г. в Wayback Machine.
^ Методы на основе графов в компьютерном зрении: разработки и приложения , с. 58
^ Нойхаус, Мишель; Бунке, Хорст (2007). Преодоление разрыва между расстоянием редактирования графа и машинами с ядром . Всемирная научная. п. 16. ISBN 981-270-817-0 . Архивировано из оригинала 30 декабря 2022 года . Проверено 30 декабря 2022 г.
^ Jump up to: Перейти обратно: ^а ^б Хорст Бунке, Сяои Ян, «Сопоставление графов и сходство», в: Интеллектуальные системы и интерфейсы , стр. 281–304 (2000). дои : 10.1007/978-1-4615-4401-2_10

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[endikaCh2-1] Jump up to: Перейти обратно: ^а ^б ^с Эндика Бенгоэчеа, «Неточное сопоставление графов с использованием оценки алгоритмов распределения». Архивировано 11 января 2017 г. в Wayback Machine , Ph. D., 2002, Глава 2: Проблема сопоставления графов. Архивировано 16 мая 2017 г. на Wayback Machine (получено 28 июня 2017 г.).

[endikaAbstract-2] Эндика Бенгоэчеа, доктор философии, реферат заархивирован 11 января 2017 г. в Wayback Machine.

[3] Методы на основе графов в компьютерном зрении: разработки и приложения , с. 58

[4] Нойхаус, Мишель; Бунке, Хорст (2007). Преодоление разрыва между расстоянием редактирования графа и машинами с ядром . Всемирная научная. п. 16. ISBN 981-270-817-0 . Архивировано из оригинала 30 декабря 2022 года . Проверено 30 декабря 2022 г.

[hbxj-5] Jump up to: Перейти обратно: ^а ^б Хорст Бунке, Сяои Ян, «Сопоставление графов и сходство», в: Интеллектуальные системы и интерфейсы , стр. 281–304 (2000). дои : 10.1007/978-1-4615-4401-2_10

[1]

[2]

[3]

[4]

[5]