Cтраница 3
В самом деле, произвольное независимое множество С в Г может быть представлено в виде С A U В, где А С Г Х, В С П Z. [31]
При представлении игр графами независимое множество вершин является таким множеством позиций, что никакая из них не может быть достигнута из другой за один ход. [32]
Доклад посвящен оценкам числа независимых множеств в графах. Подмножество А вершин графа G называется независимым, если в графе отсутствуют ребра, оба конца которых лежат в А. [33]
Доказать, что подмножество аффинного независимого множества аффинно независимо. [34]
Один из способов нахождения наибольшего независимого множества вершин графа О ( X, Г) состоит в построении всех максимальных независимых множеств вершин и выборе из них множества с наибольшей мощностью. [35]
Один из способов нахождения наибольшего независимого множества вершин графа G ( X, Г) состоит в построении всех максимальных независимых множеств вершин и выборе из них множества с наибольшей мощностью. [36]
Можно сделать задачу о независимом множестве с максимальным весом более осмысленной, исключив сформулированное выше тривиальное решение и предположив, что матроид на самом деле не задан полностью заранее, а задан только в определенном следующем смысле. Пусть нам даны множество S его вершин ( вместе с их весами) и оракул, или подпрограмма, для проверки, является ли то или иное подмножество X из S независимым или нет. [37]
Следует подчеркнуть, что топологически независимые множества не имеют общих точек. Однако, если оба множества открьгы или же оба замкнуты, то отсутствия у них общих точек уже достаточно для их топологической независимости: нужно лишь учесть, что открытое множество является окрестностыи любой своей точки, - замкнутое - содержит все свои точки косновения. [38]
Отметим также, что каждое независимое множество С - У можно расширить до базы В 3 С; достаточно поочередно добавлять в С новые элементы, присоединение которых не нарушает независимости, вплоть до момента, когда таких элементов больше не существует. [39]
Следствие 5.6. Если А - независимое множество, то для произвольного е е Е множество А [) е содержит не более одного цикла. [40]
Частичное упорядочение, в котором наибольшие независимые множества состоят из 6 элементов, имеет независимое разложение на упорядочения. [41]
Для доказательства второго равенства рассмотрим независимое множество Mlt содержащее Pi ребер. Тогда реберное покрытие Y получим, если возьмем объединение множества М1 и множества тех ребер графа G, которые инцидентны вершинам, не покрытым ребрами множества MI. [42]
Доказать или опровергнуть: каждое независимое множество ребер содержится в наибольшем независимом множестве ребер. [43]
В связи с этим максимальное линейно независимое множество наз. [44]
G В) является семейством независимых множеств некоторой предгеометрии G В на множестве В, называемой сужением G на В. [45]