МУ к ДЗ - Формальное представление схем электрических принципиальных для решения задач (1065422), страница 4
Текст из файла (страница 4)
5.2, б). хд Х4 хд а Рве. 5.2. Мультяграф Пусть задан граф С = (Х, У) без петель и кратных ребер. Раскраской вершин графа С = (Х,У) называется такое разбиение множества его вершин на р непересе- Р кающихся подмножеств Хд,Хд, ...,ХР, Х = ЦХ,; Х; й Х = 9; д Ф/; (,д Е (1,2, ...,р), У 1 при котором каждое подмножество Х~ не содержит смежных вершин, т.е.
ЮХ;(х~Йх ). Если каждому подмножеству Х; поставить в соответствие определенную «краску», то вершины этого подмножества можно окрасить в один цвет, вершины другого — в дру- 14 гой цвет и т.д. Иными словами, любая пара смежных вершин окрашивается в разные цвета. Наименьшее число подмножеств, на которое можно разбить множество вершин графа при раскраске, называется хромапдическим числом ЦС) графа С.
Например, множество вершин графа (рис. 5.3) можно разбить не менее чем на три непересекающихся подмножества: Хд = (хд,хз,хе), Хг = (хг,х4), Хз = (хв) Следовательно, хроматическое число рассматриваемого графа ДС) = 3 и граф можно раскрасить тремя красками. Хд Х5 Х4 Рис. 5З. Граф с хроматическим числом С(й) = 3 Существенной характеристикой графа является его связность. Предварительно дадим определение маршрута, цепи и цикла. Последовательность ребер У; Е У, 'заданных парами вершин вида (хо, хд), (хд, хг), ..., (х; д, х;), в которой любые два соседних ребра смежные, называется маридрутом. Число ребер в маршруте определяет его длину. Если все ребра в маршруте различны, то такой маршрут является цепьдо.
Вершины в цепи могут повторяться несколько раз. Если в цепи нет повторяющихся вершин, кроме соседних, то такая цепь называется простой. Цепь, в которой совпадают начальная и конечная вершины, называется циклом. Для ориентированных графов справедливы понятия как ориентированных цепей и циклов, так и неориентированных.
В первом случае, при рассмотрении цепи или цикла, дуги проходят только в направлении их ориентации, во втором ориентация во внимание не принимается. Ориентированную цепь называнп иногда путем, а ориентированный цикл — контуром. Две вершины хь х Е Х, д ~ ) графа С = (Х, У) называются связными, если их можно соединить маршрутом. Граф С = (Х, У) называется связным, если любые две его вершины связаны маршрутом (см. рис. 5.1, а).
Если взять какую- либо вершину х; к Х графа С = (Х, У) и построить подмножество Х' ~ Х, состоящее из всех вершин, которые можно соединить с х; произвольным маршрутом, причем х; включается в Х', то подграф С' = (Х', У), образованный на множестве вершин Х', называется компонентой связности графа С. Заметим, что связный граф состоит из единственной компоненты связности. Если граф имеет несколько компонент связности, то он не связан, так как вершины из разных компонент связности нельзя соединить маршрутом.
Так, для графа, показанного на рис. 5.4, можно назвать четыре компоненты связности: Хд = (хи хг, хз,х4), Хг = (хв,хе,хг,хв) Хз = (хо хдо, хдд), Х4 = (хдг) 15 хо Х12, -", "1о ',о') хз Хп хв Рно. 5.4. Связный граф е нооколькимн компонентами связности При этом справедлива следующая запись: х=Дх,,Пх, где 1 = 1, 2, 3, 4; Х вЂ” множество вершин графа а. Можно также сказать, что компонента связности — это связная часть несвязного графа.
Говоря о частях графа, можно выделить следующие основные понятия: частичный граф и подграф. Частичный граф — это такой граф, у которого по отношению к исходному графу удалены некоторые ребра. Таким образом, граф С' будет частичным графом С, если с = (х,и),а'= (х,и'),и'а и Подграф — это такой граф, у которого по отношению к исходному графу удалены некоторые вершины и ребра, им инциндентные.
Так, С' будет подграфом графа С, если а = (х, и), с' = (х', и'), х' с х, и' с и Компоненты связности несвязного графа есть подграфы общего графа. Двудольный граф (граф Еержа) — это граф, множество вершин которого распадается на два непересекающихся подмножества так, что ребра графа соединяют вершины только из разных подмножеств (рис. 5.5).
Особый интерес представляют граф-деревья. Граф-дерево — зто конечный связный неориентированный граф, не имеющий циклов и содержащий не менее двух вершин, соединенных ребром (рис. 5.6). Любая цепь в графе-дереве является простой н будет графом без циклов. х, хо х, Х2 хо ХЗ хз Х4 хо Рнс. 5.5.
Граф Берио Рис. 5.6. Граф-дерево 16 Чтобы любой связный граф преобразовать в граф-дерево, из него надо исключить ребра, образующие в графе циклы. Для определения количества циклов в графе (или количества ребер, образующих эти циклы) пользуются понятием никломатического числа графа, которое можно определить по формуле у(С) = т — и+ к, где т — число ребер графа; и — число его вершин; 1с — число компонент связности, для связного графа й = 1.
На рис, 5.7 изображены связный граф и образованное из него исключением двух ребер граф-дерево. хз х, х, х4 хз а) б) Рис. 5.7. Виды графов. в — сввзвый граф; 6 — граф-дерево 'Ъ Граф-деревья обладают следующими свойствами: 1) в дереве две любые вершины связаны единственной цепью; 2) любое дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.
Вершина х; графа С называется концевой, если р(х~) = 1, т.е. существует единственное ребро и(хь х1) с концом в хо Такое ребро называют концевым; 3) число св различных деревьев, которые можно 1юстроить на и заданных вершинах, рассчитывается по формуле г = ив-2 в 4) для любого графа-дерева выполняется соотношение и — т= 1 где и — число вершин, т — число ребер; 5) граф-деревья всегда плоские.
Граф называется плоским, если его можно изобразить на плоскости так, чтобы все пересечения ребер происходили только в вершинах. Граф на рис. 5.8 плоский, на рис. 5.9 неплоский. х$ х5 Рис. 5.9. Псплосквй граф Рвс. 5.5. Плоский граф Имеет место несколько способов представления графа: 1) геометрический; 2) аналитический: 17 а) в виде отображений и соответствий; б) трехместного предиката или инцидентора; в) матричный. Геометрическое представление графа наглядно, но не всегда удобно. Например, при решении задач на ЭВМ вся исходная информация должна быть переведена в аналитическую форму.
Для графов существует несколько аналитических способов их задания. 1 способ. Если задано множество вершин Х и отображений Г, то в этом отображении каждой вершине х~ Е Х соответствует множество вершин графа, связанных с вершиной х~ ребрами. Отсюда определим граф 6 = (Х, Г). Для графа (см. рис. 5.1, а) справедливы следующие соотношения: Х = (хз хз хз. хф. хз), Г„, = (хз, хз„хф„хз), Г„, = (хм хф, хз), Г„, = (хо хз), Гх+ (хц хз, хз)э Гхз (хз, хз, хз, х4) 11 способ.
Граф можно задать также с помощью двух множеств — множества вершин, множества ребер и предиката или инцидентора, указывающего, какую пару вершин соединяет то или иное ребро: где Х = (хм ха, ...,х„) — множество вершин; У = (из,из, ...,и~) — множество ребер; Р = (хьиз, хД вЂ” предикат графа; ~ = 1, и;/ = 1, и; к = 1, т 111 способ. Другой из аналитических способов — матричный (задание графа матрицами различного рода).
Каждый граф можно полноспю описать одной из трех матриц: смежности вершин, смежности ребер, инцидвнтности. Матрица смежности вершин А — это квадратная матрица размерами п х и, где и — число вершин графа. Матрица смежности вершин А=йа~Д „; где а~ — элемент матрицы А, лежащий на пересечении )-й строки и)'-го столбца, ~,1 = 1, и, причем 1,еслих;йх ау = О, если х~ й х ' где й — бинарное отношение.
Если граф имеет кратные ребра, то числа 1 и О можно заменить кратностями ребер, соединяющих соответствующие вершины. Машрипа смежности ребер Ф вЂ” это квадратная матрица размером мха, где т— число ребер графа. Матрица смежности ребер: Иг = Ои;Д где и;~ — элемент матрицы И~, лежащий на пересечении ~-й строки и )-го столбца, 1,1 = 1,т, причем 1 , если У; Н У. О, если У; й У~ Матрица инцидентности Б — это прямоугольная матрица размерами т х п, где п — число вершин графа; т — число ребер графа. Матрица инцидентности: Г8 где ео — элемент матрицы 5, лежащий на пересечении 1-й строки и 1'-го столбца, 1= 1,п;1= 1,т, причем 1, если х~ й ит 80 = 1 О,если х; В и.
Для ориентированного графа можно принять следующие значенияз;: О 1 1, если и1 исходит из х; -1, если и. заходит в х; 0 если ит не инцидеитно х; На рис. 5.10 изображен граф и описание этого графа с помощью перечисленных матриц. х2 х, х 1 2 3 4 5 16 Рис. 5.10. Графа и его матричное описание 5.3. Формальное описание коммутационных схем Учитывая характер основных задач конструирования, можно рассматривать исходную схему электрическую принципиальную как некоторое множество элементов Х = (хыхг, ...,х„), соединенных между собой электрическими цепями из множества У = (иыиз, ...,и,а).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
