In mathematics, the Bron–Kerbosch algorithm is a technique for finding maximal cliques in an undirected graph. It was designed by Dutch scientists Joep Kerbosch and Coenraad Bron.

PropertyValue
dbpprop:abstract
  • In mathematics, the Bron–Kerbosch algorithm is a technique for finding maximal cliques in an undirected graph. It was designed by Dutch scientists Joep Kerbosch and Coenraad Bron.
  • Алгоритм Брона-Кербоша - алгоритм поиска всех клик (а так же максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик. Полным подграфом неориентированного графа называется подмножество вершин, каждые две из которых соединены ребром. Полный подграф называется максимальным (по включению) полным подграфом или кликой если он не содержится полностью ни в одном другом полном подграфе исходного графа (иными словами, если при добавлении к нему еще одной вершины исходного графа он перестает быть полным) Независимым множеством вершин графа называется подмножество вершин, никакие две из которых не соединены. Независимое множество вершин называется максимальным независимым (по включению) множеством вершин если оно не содержится полностью ни в одном другом независимом множестве вершин исходного графа (иными словами, если при добавлении к нему еще одной вершины исходного графа оно перестает быть независимым) Легко показать, что задача о клике и задача о независимом множестве по сути эквивалентны: каждая из них получается из другой, путем построения дополнения графа — такого графа, в котором есть все вершины исходного графа, причем в дополнении графа вершины соединены ребром тогда и только тогда, если они не были соединены в исходном графе.
rdfs:comment
  • In mathematics, the Bron–Kerbosch algorithm is a technique for finding maximal cliques in an undirected graph. It was designed by Dutch scientists Joep Kerbosch and Coenraad Bron.
  • Алгоритм Брона-Кербоша - алгоритм поиска всех клик (а так же максимальных по включению независимых множеств вершин) неориентированного графа.
rdfs:label
  • Bron–Kerbosch algorithm
  • Алгоритм Брона — Кербоша
skos:subject
foaf:page
is dbpprop:redirect of