Теория графов и комбинаторика

1;ограк'1т;ай rpaij-a называется ко:- ,йнща неко орой его 0 - Цсп;:. Ког|вклце1' ^1Нояеотва вершин $><^\/ назнзаетоя кограняда 0-цопи 2Г т)"^ , где г/i е 5 . Ког|)агаща мяо.ж0отва S еоть шго- лестло роех . эсЗер, ооадиняющах ':чршя:щ шожеотва S о вершками ; •AS V \ S . Кажлсая когрангца является разрезом. Шюжвство всех кох'рйяиц называется лроотрзнотвом разр^пов графа. Базис этого проетрэкоч'ва называо'?оя безпеом хазрззов (коцикло '• и содержит t f ) кограниц. Вуоть ^ =С\/,у) - овязный граф. йкоцентриоитетом верши­ ны ТГ ё V" иааызаетоя число б CV") : Г С Г Г ) = 9(ir,vr) . • Радйуо tCG-) графа - это наименьший из экоцантриоитэтов его верптк . , Х.С&) = vvtLn e c u - j . ITFEV ^ Диаметром графа называется наибольший из экоцент- • рисятетов его варяпк с1шСб)= vvip^ вСгг) . Иногда дааметр опредв.тают icaic величину, равную удвоенном;, радиусу. Вершина V называется центральной, воли eCif)=' f C & ) . М'-ожество воех ' • центральнах вершин называется центром графа. Для деравьев огфа- - ведлива Тбоиема 9 . 6 . Центр лкхЗоГ'-^ дерева содержит либо. одну верши-, ну, либо две oweaHHQ BeismiHH. . Доказятельотво.Ёоли Т - дерево, то, удалив вое виоячиа вершины, полз'т ч дерево Т ' ' • кмеющев тот же центр. Дейотшхеоп.- йо, в (9.1) максимум достигается на висячих ве1шнах, поэтому удаление висячих вершин уменьшает эксцентриситеты всех остальных верюия на единицу и не наменяет центра. Повторяя этот цроцаос, напучим пооледовательнооть деревьев Т,Т', Т ' " . , имекицах один а тот же центр. Последним элементом этой посыхедовательноо- • тп будет либо , либо . Но каждая вершина s t<^i и явля- етоя центральной, ijiyoTb V ~ дерево. Ветвью к ворпина 2ЛеТказывавтоя мэжоиыальг- ное поддерево f Ct^} , оодаржащее в качестве висячей вершины.. Очевидно, число ветвей к вершине 1Г равно степени этой, вернШЕИ. - . • , « О •