Ребро - граф
Cтраница 2
Ребрам графа G приписаны положительные веса. [16]
Ребром графа или подграфа может, быть любой элемент технологического объекта или объект в целом, если для него можно указать одну точку входа. [17]
Если ребра графа ориентированы, то есть характеризуются направлением и изображаются стрелкой, то их принято называть дугами. [18]
Каждое ребро графа соответствует паре соседних букв слова х, так что слово х и является эйлеровым контуром. [19]
Упорядочить ребра графа О в порядке неубывания их весов. [20]
Каждое ребро графа О принадлежит в точности одному 3-блоку графа О относительно ребра А. Каждое виртуальное ребро графа С относительно ребра А встречается в двух 3-блоках - в одном как отдушина, а в другом как перемычка. [21]
Каждое ребро графа / (, окрашено в один из п цветов таким образом, что каждая вершина инцидентна ровно одному ребру каждого цвета. [22]
Если ребра графа ориентированы, то есть характеризуются направлением и изображаются стрелкой, то их принято называть дугами. [23]
Пусть ребра графа правильно раскрашены и пусть х и у - два различных цвета. Двухцветной ( х, у) - цепью назовем элементарную цепь, состоящую из ребер графа, окрашенных в цвета х и у. Понятно, что цвета х и у на такой цепи чередуются. Двухцветная цепь может, в частности, состоять из одной вершпны, из одного ребра или быть элементарным циклом. Нетрудно убедиться в том, что две максимальные ( х, г /) - цепи ( с одной и той же парой цветов х, у) не могут иметь общих вершин. Отсюда, в частности, следует, что перекраска любой максимальной двухцветной цепи правильно раскрашенного графа не нарушает правильности его раскраски. А; если же у - конец максимальной ( х, у) - цепи А, содержащей хотя бы одно ребро, то в М один из цветов х или у заменяется при перекраске другим. [24]
Подразобьем ребро графа G двумя новыми вершинами, если при этом не возникает i / 1 непересекающихся Т - разрезов; будем продолжать эту процедуру до тех пор, пока это возможно. Поскольку, как мы ранее убедились, никакое ребро не будет подразбито более чем v вершинами, то за конечное число шагов мы получим граф G, не имеющий v 1 реберно непересекающихся Т - разрезов. Отметим, что граф G является также двудольным и каждый Т - разрез в G имеет не менее двух ребер. [25]
Упорядочить ребра графа G в порядке неубывания их весов. [26]
Каждое ребро графа G соединяет две вершины. Таким образом, суммируя степени всех вершин, мы можем подсчитать и количество ребер графа. Следовательно, сумма степеней всех вершин равна удвоенному числу ребер в простом графе. [27]
Множество ребер графа обычно обозначают через Е, а величина Е определяет сложность объекта граф: чтобы задать граф, нужно каким-то образом перечислить его ребра. [28]
 |
Виды графа. а - ориентированный, 6 - неориентированный, в - смешанный. [29] |
Последовательность ребер графа, в которой два соседних ребра имеют общую вершину, называют маршрутом. Если начало и конец маршрута находятся в одной вершине, то такой маршрут называется циклическим. Если в каждом маршруте каждое ребро встречается только по одному разу, то такой маршрут называется цепью. Цепи по функциональным свойствам различают: размерные, динамические, кинематические, электрические и электронные. Если цепь замкнута, т.е. начинается и оканчивается в одной и той же вершине, то она называется циклом. Примером цикла служит электрическая цепь, отсюда возникли электромеханические, электрогидравлические и другие аналогии. Если каждую вершину можно соединить с любой другой вершиной некоторой цепью, то граф называется связным. Связной граф, не содержащий циклов и не имеющий кратных ребер, называется деревом. [30]
Страницы: 1 2 3 4 5