Пусть имеется цепь, связывающая две вершины. Количество ребер, входящих в цепь, называется расстояниемd(U, V), где U и V – концы цепи.
Так как количество вершин конечно, то количество цепей тоже конечно, следовательно, расстояние ограничено снизу и сверху, а значит, существует цепь с кратчайшим расстоянием, которая называется геодезической.
Наибольшее из расстояний называется диаметром графа.
Вершины, находящиеся на одном и том же расстоянии от заданной вершины, образуют ярус.
Полный граф – граф, у которого любые две вершины смежены.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление