Independence number
http://dbpedia.org/resource/Independence_number
Число независимости графа — это размер наибольшего независимого множества вершин в нём. Поскольку задача о независимом множестве является NP-полной, то неизвестны алгоритмы определения числа независимости в произвольном графе, работающие за полиномиальное время. В графе , в котором отсутствуют изолированные вершины (вершины степени 0), также справедливо неравенство , где — число рёберного покрытия графа . В двудольном графе без изолированных вершин, вследствие Теоремы Кёнига, .
rdf:langString
Число́ незале́жності або число́ вну́трішньої щі́льності графа — це розмір найбільшої незалежної множини вершин у ньому. Оскільки задача про незалежну множину є NP-повною, то невідомі алгоритми визначення числа незалежності в довільному графі, що працюють за поліноміальний час. У графі , в якому відсутні ізольовані вершини (вершини степеня 0), також виконується нерівність , де — число реберного покриття графа . У двочастковому графі без ізольованих вершин, унаслідок теореми Кеніга, .
rdf:langString
rdf:langString
Stabilitätszahl
rdf:langString
Independence number
rdf:langString
Число независимости
rdf:langString
Число незалежності
xsd:integer
5526051
xsd:integer
955558843
rdf:langString
Число независимости графа — это размер наибольшего независимого множества вершин в нём. Поскольку задача о независимом множестве является NP-полной, то неизвестны алгоритмы определения числа независимости в произвольном графе, работающие за полиномиальное время. В любом графе число независимости связано с числом вершинного покрытия первым тождеством Галлаи: , более того, дополнение к наибольшему независимому множеству вершин является наименьшим вершинным покрытием. Используя этот факт, в двудольном графе можно найти за полиномиальное время, поскольку задача о наименьшем вершинном покрытии в нём сводится к поиску наибольшего паросочетания. В графе , в котором отсутствуют изолированные вершины (вершины степени 0), также справедливо неравенство , где — число рёберного покрытия графа . В двудольном графе без изолированных вершин, вследствие Теоремы Кёнига, .
rdf:langString
Число́ незале́жності або число́ вну́трішньої щі́льності графа — це розмір найбільшої незалежної множини вершин у ньому. Оскільки задача про незалежну множину є NP-повною, то невідомі алгоритми визначення числа незалежності в довільному графі, що працюють за поліноміальний час. У будь-якому графі число незалежності пов'язане з числом вершинного покриття першою тотожністю Галлаї: , більш того, доповнення до найбільшої незалежної множини вершин є найменшим вершинним покриттям. Використовуючи цей факт, у двочастковому графі можна знайти за поліноміальний час, оскільки задача про найменше вершинне покриття в ньому зводиться до пошуку найбільшого парування. У графі , в якому відсутні ізольовані вершини (вершини степеня 0), також виконується нерівність , де — число реберного покриття графа . У двочастковому графі без ізольованих вершин, унаслідок теореми Кеніга, .
xsd:nonNegativeInteger
74