Поиск изоморфных подграфов - История изменений

ASA в 14:03, 6 марта 2018

2018-03-06T14:03:06Z

← Предыдущая версия		Версия от 14:03, 6 марта 2018
Строка 1:		Строка 1:
			{{level-p}}

	== Постановка задачи ==		== Постановка задачи ==

ASA в 11:18, 29 июля 2015

2015-07-29T11:18:10Z

← Предыдущая версия		Версия от 11:18, 29 июля 2015
Строка 18:		Строка 18:

	<references />		<references />

			[[Категория:Статьи в работе]]

Daryin: /* Постановка задачи */

2015-07-07T09:13:46Z

Постановка задачи

← Предыдущая версия		Версия от 09:13, 7 июля 2015
Строка 1:		Строка 1:
	== Постановка задачи ==		== Постановка задачи ==

	Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, ~~изоморфных~~ <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.		Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфный <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.

	== Свойства задачи ==		== Свойства задачи ==

Daryin: Алгоритм Ульмана вынесен в отдельную статью, добавлен VF2

2015-06-18T15:51:02Z

Алгоритм Ульмана вынесен в отдельную статью, добавлен VF2

← Предыдущая версия		Версия от 15:51, 18 июня 2015
Строка 1:		Строка 1:
	== ~~Свойства и структура алгоритмов ==~~		== Постановка задачи ==
	~~=== Общее описание алгоритма =~~==

	Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфных <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.		Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфных <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.

			== Свойства задачи ==

	Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.		Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.

	'''Алгоритм Ульмана'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом		== Алгоритмы решения задачи ==

			'''[[Алгоритм Ульмана]]'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
	* для фиксированного графа <math>H</math> время полиномиальное;		* для фиксированного графа <math>H</math> время полиномиальное;
	* для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).		* для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).

	~~=== Математическое описание ===~~		'''[[Алгоритм VF2]]'''<ref>Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.</ref> разработан специально для применения на больших графах.
	~~=== Вычислительное ядро алгоритма ===~~
	~~=== Макроструктура алгоритма ===~~
	~~=== Описание схемы реализации последовательного алгоритма ===~~
	~~=== Последовательная сложность алгоритма ===~~
	~~=== Информационный граф ===~~
	~~=== Описание ресурса параллелизма алгоритма ===~~
	~~=== Описание входных и выходных данных ===~~
	~~=== Свойства алгоритма===~~
	~~== Программная реализация алгоритмов ==~~
	~~=== Особенности реализации последовательного алгоритма ===~~
	~~=== Описание локальности данных и вычислений ===~~
	~~=== Возможные способы и особенности реализации параллельного алгоритма ===~~
	~~=== Масштабируемость алгоритма и его реализации ===~~
	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~
	~~=== Выводы~~ для ~~классов архитектур ===~~
	~~=== Существующие реализации алгоритма ===~~
	== Литература ==		== Литература ==

	<references />		<references />

Daryin: Общее описание алгоритма

2015-06-09T23:32:42Z

Общее описание алгоритма

Новая страница

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

Пусть заданы два графа <math>G</math> и <math>H</math>. '''Задача поиска изоморфных подграфов''' состоит в том, чтобы определить, существует ли у графа <math>G</math> подграф, изоморфных <math>H</math>, и в случае положительного ответа – предъявить хотя бы один такой подграф.

Задача поиска изоморфных подграфов является NP-полной, поэтому не существует известных алгоритмов, решающих её за полиномиальное время.

'''Алгоритм Ульмана'''<ref>Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.</ref><ref>Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.</ref> решает задачу поиска изоморфных подграфов за экспоненциальное время, при этом
* для фиксированного графа <math>H</math> время полиномиальное;
* для планарного графа <math>G</math> время работы линейное (при фиксированном графе <math>H</math>).

=== Математическое описание ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />