Cтраница 4
А и В, если каждая связывающая простая цепь должна проходить хотя бы через одну вершину из S. Заметим, что каждое разделяющее множество содержит минимальное разделяющее множество. Множества А п В называются а-вер-шинпо разделенными, если существует конечное разделяющее множество (12.2.2) с минимальным числом а вершин. [46]
Они называются соответственно подпространствами разделяющего множества и цикла и, согласно равенству ( 4), являются ортогональными в случае евклидова внутреннего произведения. [47]
Все ати определения легко переносятся на несвязные графы. В произвольном графе G разделяющим множеством называется такое множество ребер, удаление которого увеличивает число компонент в G. Разрезом в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. [48]
Каждая дуга связывает два узла. Поэтому если удалять одну за другой дуги приведенного разделяющего множества, то число компонент связности каждый раз либо не меняется, либо увеличивается на единицу. [49]