Лексикографический поиск в ширину - История изменений

Patarakin в 07:59, 20 октября 2022

2022-10-20T07:59:53Z

← Предыдущая версия		Версия от 10:59, 20 октября 2022
Строка 1:		Строка 1:
	'''Лексикографический поиск в ширину''' — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма [[Поиск в ширину\|поиска в ширину]] и дает более упорядоченную последовательность вершин графа.		'''Лексикографический поиск в ширину''' — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма [[Поиск в ширину\|поиска в ширину]] и дает более упорядоченную последовательность вершин графа.

	Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения\| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004)~~{{sfnp\|Corneil\|2004}}.~~ Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание [[Хордальный граф\| хордальных графов]], [[Раскраска графов\| раскраска]] [[Дистанционно-наследуемый граф\|полностью расщепляемых графов]].		Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения\| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004) Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание [[Хордальный граф\| хордальных графов]], [[Раскраска графов\| раскраска]] [[Дистанционно-наследуемый граф\|полностью расщепляемых графов]].

	~~[[Файл~~:LBFS_2.gif~~\|thumb\|Пример работы алгоритма~~.]]		https://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/LBFS_2.gif/330px-LBFS_2.gif

	== Описание алгоритма ==		== Описание алгоритма ==
Строка 27:		Строка 27:
	Для распознавания [[Интервальный граф\|единичных интервальных и интервальных графов]] используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз).		Для распознавания [[Интервальный граф\|единичных интервальных и интервальных графов]] используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз).

	~~== Примечания ==~~
	~~{{примечания}}~~

	~~== Литература ==~~		----
	* {{citation
	~~\| last1 = Brandstädt \| first1 = Andreas \| author1~~-~~link = Andreas Brandstädt~~
	~~\| last2 = Le \| first2 = Van Bang~~
	~~\| last3 = Spinrad \| first3 = Jeremy~~
	~~\| title = Graph Classes: A Survey~~
	~~\| publisher = SIAM Monographs on Discrete Mathematics and Applications~~
	~~\| year = 1999~~
	~~\| isbn = 0~~-~~89871~~-~~432~~-~~X}}.~~
	* {{citation\|first1=Anna\|last1=Bretscher\|first2=Derek\|last2=Corneil\|author2-link=Derek Corneil\|first3=Michel\|last3=Habib\|first4=Christophe\|last4=Paul\|title=A simple linear time LexBFS cograph recognition algorithm\|journal=[[SIAM Journal on Discrete Mathematics]]\|volume=22\|issue=4\|year=2008\|pages=1277–1296\|doi=10.1137/060664690\|url=http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps}}.
	* {{citation\|first=Derek G.\|last=Corneil\|authorlink=Derek Corneil\|contribution=Lexicographic breadth first search – a survey\|title=Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers\|publisher=Springer-Verlag\|series=Lecture Notes in Computer Science\|volume=3353\|year=2004\|pages=1–19\|doi=10.1007/978-3-540-30559-0_1}}.
	* {{citation\|first1=Michel\|last1=Habib\|first2=Ross\|last2=McConnell\|first3=Christophe\|last3=Paul\|first4=Laurent\|last4=Viennot\|title=Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing\|journal=Theoretical Computer Science\|volume=234\|year=2000\|pages=59–84\|url=http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf\|issue=1–2\|doi=10.1016/S0304-3975(97)00241-7\|archiveurl=https://web.archive.org/web/20110726091134/http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf\|archivedate=2011-07-26\|access-date=2016-06-07}} {{Wayback\|url=http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf \|date=20110726091134 }}.
	* {{citation\|first1=D. J.\|last1=Rose\|first2=R. E.\|last2=Tarjan\|author2-link=Robert Tarjan\|first3=G. S.\|last3=Lueker\|year=1976\|title=Algorithmic aspects of vertex elimination on graphs\|journal=[[SIAM Journal on Computing]]\|volume=5\|pages=266–283\|issue=2\|doi=10.1137/0205021}}.

	~~{{Алгоритмы поиска на графах}}~~

	~~[[Категория:Алгоритмы поиска на графах]]~~
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]

Patarakin в 07:57, 20 октября 2022

2022-10-20T07:57:40Z

← Предыдущая версия		Версия от 10:57, 20 октября 2022
Строка 1:		Строка 1:
	'''Лексикографический поиск в ширину''' ~~({{lang-en\|lexicographic breadth-first search}}, '''LBFS or Lex-BFS''')~~ — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма [[Поиск в ширину\|поиска в ширину]] и дает более упорядоченную~~{{термин}}~~ последовательность вершин графа.		'''Лексикографический поиск в ширину''' — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма [[Поиск в ширину\|поиска в ширину]] и дает более упорядоченную последовательность вершин графа.

	Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения\| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004){{sfnp\|Corneil\|2004}}. Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание [[Хордальный граф\| хордальных графов]], [[Раскраска графов\| раскраска]] [[Дистанционно-наследуемый граф\|полностью расщепляемых графов]].		Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения\| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004){{sfnp\|Corneil\|2004}}. Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание [[Хордальный граф\| хордальных графов]], [[Раскраска графов\| раскраска]] [[Дистанционно-наследуемый граф\|полностью расщепляемых графов]].

Patarakin: 1 версия импортирована

2022-10-19T17:55:03Z

1 версия импортирована

← Предыдущая версия		Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>Михаил Кораблев в 09:03, 23 сентября 2021

2021-09-23T09:03:10Z

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

'''Лексикографический поиск в ширину''' ({{lang-en|lexicographic breadth-first search}}, '''LBFS or Lex-BFS''') — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма [[Поиск в ширину|поиска в ширину]] и дает более упорядоченную{{термин}} последовательность вершин графа.

Алгоритм лексикографического поиска в ширину основан на идее [[Уточнение разбиения| разбиения на подмножества]] и впервые был разработан Роузом, Тарьяном и Люкером (1976). Более детальный обзор темы был представлен Корнейлом (2004){{sfnp|Corneil|2004}}. Лексикографический поиск в ширину используется как часть в других графических алгоритмах, например, распознавание [[Хордальный граф| хордальных графов]], [[Раскраска графов| раскраска]] [[Дистанционно-наследуемый граф|полностью расщепляемых графов]].

[[Файл:LBFS_2.gif|thumb|Пример работы алгоритма.]]

== Описание алгоритма ==
Для работы алгоритма необходимо задать вершину графа, с которой начинается обход. Описание алгоритма выглядит следующим образом:

* Инициализировать последовательность множеств вершин Σ состоящую из одного множества содержащего все вершины графа.
* Инициализировать пустую выходную последовательность вершин.
* Пока Σ непустое:
** Из первого множества в Σ взять вершину ''v'' и удалить ее из множества.
** Если первое множество в Σ стало пустым удалить его из Σ .
** Добавить ''v'' в конец выходной последовательности вершин.
** Для каждого ребра ''v-w'':
*** Определить множество ''S'' в Σ которое содержит ''w''.
*** Если множество ''S'' еще не разделялось при обработке ''v'', создать новое пустое множество ''T'' и поместить его перед ''S'' в Σ.
*** Переместить вершину ''w'' из ''S'' в ''T'' и, если ''S'' стало пустым удалить его из Σ.

Каждая вершина обрабатывается один раз, каждое ребро тестируется только при обработке его двух вершин, и (в предположении, что обработка операций в последовательности множеств Σ занимает конечное время) каждая итерация внутреннего цикла занимает конечное время. Значит, также как и для алгоритмов [[Поиск в глубину| поиска в глубину]] и [[Поиск в ширину| поиска в ширину]] [[временная сложность]] алгоритма является линейной и составляет <math>O(\vert V \vert + \vert E \vert)</math>.

Алгоритм называется лексикографическим поиском в ширину потому, что получаемый порядок похож на результат алгоритма [[Поиск в ширину| поиска в ширину]], но дополнительно строки и столбцы [[Матрица смежности|матрицы смежности]] [[Алгоритм сортировки|сортируются]] в [[Лексикографический порядок|лексикографическом порядке]].

== Применение ==
Алгоритм лексикографического поиска в ширину используется для распознавания [[Хордальный граф| хордальных графов]], [[Раскраска графов| раскраски]] [[дистанционно-наследуемый граф|вполне сепарабельных графов]].
Для распознавания [[Интервальный граф|единичных интервальных и интервальных графов]] используются многомаховые алгоритмы (алгоритм лексикографического поиска в ширину с вариациями применяется несколько раз).

== Примечания ==
{{примечания}}

== Литература ==
* {{citation
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt
| last2 = Le | first2 = Van Bang
| last3 = Spinrad | first3 = Jeremy
| title = Graph Classes: A Survey
| publisher = SIAM Monographs on Discrete Mathematics and Applications
| year = 1999
| isbn = 0-89871-432-X}}.
* {{citation|first1=Anna|last1=Bretscher|first2=Derek|last2=Corneil|author2-link=Derek Corneil|first3=Michel|last3=Habib|first4=Christophe|last4=Paul|title=A simple linear time LexBFS cograph recognition algorithm|journal=[[SIAM Journal on Discrete Mathematics]]|volume=22|issue=4|year=2008|pages=1277–1296|doi=10.1137/060664690|url=http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps}}.
* {{citation|first=Derek G.|last=Corneil|authorlink=Derek Corneil|contribution=Lexicographic breadth first search – a survey|title=Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=3353|year=2004|pages=1–19|doi=10.1007/978-3-540-30559-0_1}}.
* {{citation|first1=Michel|last1=Habib|first2=Ross|last2=McConnell|first3=Christophe|last3=Paul|first4=Laurent|last4=Viennot|title=Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing|journal=Theoretical Computer Science|volume=234|year=2000|pages=59–84|url=http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf|issue=1–2|doi=10.1016/S0304-3975(97)00241-7|archiveurl=https://web.archive.org/web/20110726091134/http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf|archivedate=2011-07-26|access-date=2016-06-07}} {{Wayback|url=http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf |date=20110726091134 }}.
* {{citation|first1=D. J.|last1=Rose|first2=R. E.|last2=Tarjan|author2-link=Robert Tarjan|first3=G. S.|last3=Lueker|year=1976|title=Algorithmic aspects of vertex elimination on graphs|journal=[[SIAM Journal on Computing]]|volume=5|pages=266–283|issue=2|doi=10.1137/0205021}}.

{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы поиска на графах]]
[[Категория:Алгоритмы поиска]]