Архимедово лето. Глава четвертая.

презри­тельно, спрыгнул и величественно удалился.

— Уходит по прямому маршруту! — заметил Вовка.

И все засмеялись.

— Так вот, — продолжал Тимофей Иринархович, — под названием путь мы с вами будем понимать линию, соединяющую два узла, из

clip_image032

clip_image034

которых один является началом дан­ного пути, а другой — его концом. От каждого узла нашей маршрутной сети можно по путям, которые и со­ставляют эту сеть, перейти к любому иному узлу этой сети. Это свойство называется связностью. Если внутри нашей системы имеется та­кой путь, удаление которого ведет к уничтожению связности, после чего наша система распадается на две отдельные системы, то такой путь мы называем мостом. Вот перед вами чертеж, на котором мы видим мост аЬч тогда как на другом чер­теже Ьс не является мостом; если его удалить, связность системы не будет нарушена. Одиночный путь, которым кончается прямой путь, будем называть тупиком, а конечный узел его — свободным концом. Если все это ясно, то теперь я укажу, что существуют особые сети, где совсем нет кольцевых марш­рутов, а есть только одни мосты и тупики. Та­кую систему путей называют деревом. Ясно, что дерево одним маршрутом обойти нельзя: зашел в первый попавшийся тупик, и гото­во — застрял!

— А если оно состоит из одного пути? — спросил Лева.

— А стоит ли отдельный путь деревом называть? —спросил дед. — Это только основа для дерева…

Лева молча пожал плечами: он, по-видимому, все-таки остался при своем мнении.

— Характерной особенностью дерева, — продолжал дедушка,— является то, что оно теряет связность, если из него изъять любой путь, потому что каждый из них либо мост, либо тупик. А ведь тупик это тоже в некотором смысле мост — он связывает нашу систему со сво­бодным концом: если тупик удалить, то этот конец останется в виде ни с чем не связанной точки. Из этого необходимо заключить, что у дерева число путей меньше. .. чем что? Кто скажет?

— Меньше числа узлов. И меньше как раз на единицу! — ответил Лева почти без запинки.

— Докажи сейчас же! — потребовал Вовка.

— Это нетрудно, — отвечал ему брат. — Возьми самое простое дерево, отрезок — вот как я сейчас дедушке говорил, — то есть от­дельный путь, который представляет собой один мост, соединяющий две точки. А из него, как из основы, можно сделать какое хочешь дерево, прибавляя к нему постепенно тупик за тупиком, превращая тем самым один из предыдущих тупиков или часть такого

Страница 10 of 11« First...1011
Category: Разное