Дискретная математика

126 сумма локальных степеней графа четна, то в кубическом графе должно быть четное число вершин. На рис 5.8 и 5.9, а) приведены примеры кубических графов. Вершина v называется изолированной вершиной, если deg(v)=0 и концевой (висящей) вершиной, если deg(v) = l, см, рис. 5.9, б). V - висящая вершина V- изолированная вершина а) б) Рис. 5.9 Полный граф с п вершинами, очевидно, является регулярным степеш! п-1. В полном графе каждая пара его вершин соединена ребром, следовательно, число ребер полного графа ровно числу . Дуга ,г называется инцидентной вершине v, если она заходит в эту вершину или исходит из нее. Для ориентированного графа G вводятся для каждой вершшы два числа deg '(v) н deg*(v), равные соответственно числу выходящих и входяш^1Х дуг для вершины v. Эти числа называются полустепенями исхода и захода ее/ршмньг V. Тогда число дуг орграфа равно: 7И= Y, deg'(v) = X deg*(Vi). v/eK VJSV Ориентированный граф называется однородным степени г, если все локальные полустепени имеют одно и то же значение: Vv, veV: deg '(v)= deg*(v) =r, ...Каклшого есть извилистых путей, А все, что нужно в этом грустном мире, - Искусство быть немножечко добрей. Э. Уткокс § 4. Цепи, циклы, пути и контуры Пусть G - неориентированный граф. Цепью в графе G называется конечная или бесконечная чередующаяся последовательность вершин и ребер Vft xj, Vj, xi, V2,..., v „.j, x^, в которой каждое ребро х, есть vi). Отметим, что одно и то лее ребро может встречаться в цепи несколько раз. ' ) Американск-ая поэтесса.