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

Рио.2.1 Если |V(<?)( = p ,1У(01-ф,, то граф б- называетояф ^ ) - г р а - фом. Иногда приходится рассматривать графы йодее оложного вида, в которых некоторые вершин могут соединяться (Золев чем одним рейром или некотсрыб вершины могут соединяться оами о ообой. Ребра, совдиняющиэ од"у и т; х.вnajy вершин, назьшаютоя кратными ресЗрами, Граф, в котором допускаются кратные peCSpa, называется мудь- тиграфом. Совокупнооть ребер мультиграфа не .зляется множеством, т . к . в множестве не может быть одинаковых элементов. Для тоге, чтобы отличить кратные ребра дкуг от друга, их нумеруют. Таким образом, мультиграфом называетоя пара множеств Q=CVfXJ , где V - конечное непустое множество вераган, а У - множэотво ребер, понима..лое как подмножество декартова прокаведенияЛ*^ Z''', где 2 ^ - множество целых положительных ч..овл. Кавдое ребро JC 1^лъ- тиграфа является упорядоченной парой вида И) , кото­ рую будем обозначать так: Здесь t'" , ' 1^ - различные вершины графа. Пример мультиграфа ^ изображен на рис.2.2. Рио.2.2 Рко.2.3 В 8Т0М графа ,х^ - кратные ребра. Еоли нумеровать кратные ребра числами, начиная о единицы, то ребра этого муль­ тиграфа можно записать в.виде: j I ) Ребро, концы которого совпадают, называется петлей. Такое ребро уже не является подмножеством множества вершин. Петлю мож­ но очитать двухэлементным подмножеотвом дизъюнктивной оумш ш о -