Cтраница 3
Мы представляем свободное дерево в виде коллекции ребер. Если представлять свободное дерево неупорядоченным, упорядоченным или даже бинарным деревом, придется признать, что в общем случае существует множество различных способов представления каждого свободного дерева. [31]
Если все концевые узлы связаны друг с другом в электротехническом смысле, то соответствующий граф будет связным в смысле теории графов. Ясно, что при минимальном числе соединительных проводов циклов быть не может, следовательно, мы должны получить свободное дерево. Согласно теореме А, свободное дерево содержит п - 1 проводов, а граф с п вершинами и п - 1 ребрами является свободным деревом тогда и только тогда, когда этот граф связен. [32]
Пусть О - ( возможно, бесконечный) граф, не содержащий циклов. Предположим, что если к G добавить какое-нибудь ребро, которого ранее в G не было, то обязательно образуется цикл. Докажите, что G является свободным деревом. [33]
После добавления таких квадратных узлов мы получили новую диаграмму, которая иногда более удобна для анализа. Ясно, что в этом увеличенном дереве каждый круглый узел имеет двух сыновей, а каждый квадратный не имеет ни одного. Если имеется п круглых и s квадратных узлов, то мы имеем п s - 1 ребер ( поскольку расширенная диаграмма представляет свободное дерево), считая же другим способом, через число сыновей, мы видим, что имеется 2п ребер. [34]
Если все концевые узлы связаны друг с другом в электротехническом смысле, то соответствующий граф будет связным в смысле теории графов. Ясно, что при минимальном числе соединительных проводов циклов быть не может, следовательно, мы должны получить свободное дерево. Согласно теореме А, свободное дерево содержит п - 1 проводов, а граф с п вершинами и п - 1 ребрами является свободным деревом тогда и только тогда, когда этот граф связен. [35]
Некоторые ребра на рис. 32 изображены более жирными линиями. Соединяя все вершины, эти ребра образуют свободное поддерево данного графа. У графов, получаемых из блок-схем, всегда можно найти свободное поддерево, поскольку такие графы должны быть связными, а согласно пункту ( Ь) теоремы А, если граф G связен и не является свободным деревом, то, убрав некоторое ребро, можно получить граф, который все еще будет связным. Этот процесс можно продолжать до тех пор, пока мы не получим поддерево. Другой алгоритм для нахождения свободного поддерева рассматривается в упр. Отметим, что сначала всегда можно отказаться от ребра е0 ( идущего от вершины конец к вершине начало), так что можно считать, что в выбранном поддереве ребра е0 нет. [36]
К сожалению, в этой области все еще не имеется стандартной терминологии, поэтому автор последовал установившейся при написании книг по теории графов традиции употреблять терминологию, подобную, но не идентичную той, которая используется во всех других книгах, посвященных теории графов. В следующих подпунктах ( как, разумеется, и во всей книге в целом) была сделана попытка выбрать среди общеупотребительных слов такие краткие и выразительные слова, которые точно передавали бы смысл важных понятий и в то же время не находились бы в противоречии с общепринятой терминологией. Принятая нами терминология ориентирована также на использование при работе с машинами; так, то, что мы называем свободным деревом инженер-электрик скорее назовет просто деревом, но нам нужно, чтобы краткий термин дерево обозначал понятие, которое обычно используется в литературе по программированию и которое поэтому имеет большое значение в вопросах программирования для ЭВМ. [37]