Главная Журналы Понятие графа служит для графического описания двух множеств, элементы одного из которых играют роль связок, соединяющих иары элементов другого множества. Строго говоря, можно считать, что задан граф Гзо] е=(л. в. С), если А - обязательно непустое множество (АФ0), именуемое множеством узлов или вершин; В - обязательно непересекающееся с множеством Л множество (Л[]В= -0), именуемое множеством ветвей или ребер; С- трехмерный инцидентор, определенный на всех тройках X, у и Ь, для которых X, уА и ЬВ (причем каждая ветвь связывает ие более ,двух в.ершин.) Применительно к теории цепей, а следовательно, и к микросхемотехнике граф электронной цепи является прймым следствием описывающей ее системы уравнений Кирхгофа: m=[Y][u]. При этом элементы матриц [I] и [U] образуют множество узлов, элементы матрицы [Y] - множество ветвей, а система уравнений задает трехмерный инцидентор. Геометрически граф изображается совокупностью произвольно расположенных точек, однозначно соответствующей множеству узлов, которая согласно закону инциденции связана совокупностью линий произвольного размера и формы, однозначно соответствующей множеству ветвей. Очевидно, что при этом один и тот же граф может быть по-разному изображен на плоскости или в пространстве, хотя его топологические свойства останутся прежними. Это свойство графа получило название изоморфизма. Оно заключается в том, что два графа считаются изоморфными, если между множествами их узлов, а также между множествами их ветвей можно установить взаимно-однозначное соответствие, сохраняющее инцидентор. Если граф можно изобразить "3 плоскости, избежав при этом пересечения ветвей, его называют плоским (планарным). Все другие графы зываются неплоскими (объемными). Граф, у которого любые два узла соединены ветвью, называется полным. Дополнением графа G является такой граф, ветви которого совместно с графом G образуют полный граф. граф, в котором -пара узлов соединяется иесколькими различными ветвями, именуют мультиграфом. Аналитически граф изображается совокупностью записей вида (х, Ь, у), которая гласит, что ветвь Ь инцидентна узлам X, у узлы х, у инцидентны ветви Ь. Ориентированным графом называется граф, ветви которого имеют строгую ориентацию. На рис. 1.1,а изображена ветвь такого графа. Ей соответствует аналитическая запись {х, Ь, у). Запись (у, Ь, х) тождественна ветви, изображенной на рис. 1.1,6. Если ветвь инцидентна одному узлу, то справедлива затаись (д;, Ь, х), ее называют петлей (рис. 1.1,б). Для ориентированных гра- а У X а. у \. J X а У о--О О-*-О -о о--о {Lj б) X в) г) Рис. 1.1. Ветви графа. а, б - направленные ветви; в - пет.чя; е - ненаправленная ветвь. фов существует следующая классификация узлш. Узлами-истоками, отображающими, как правило, независимые переменные, называют узлы, яе имеющие входящих, ветвей (т. е. стрелки инцидентных узлу ветвей направлены только от него). Узел, инцидентный только входящим в него ветвям, назьгвается узлом-стоком. Простыми именуют узлы, имеющие как входящие, так и выходящие ветви. В случае, если простмйу узлу инцидентна еще и петля, он называется смешанным. Следует отметить, что описывать электронные цепи ориентированными графами удобнее используя графы Мээона [38]. Это вызвано тем, что графы [Мэзона существенно проще в построении и Преобразовании, чем графы Коутса [7]. Учитывая это обстоятельство, во всех последующих рассуждениях понятие ориентированного графа будет отождествлено с понятием графа Мэзона. Неориентированным графом называется граф; имеющий только неориентированные ветви. Очевидно, что для его ветви (рис. 1.1,г) справедлива как запись {х, Ь, у), так и запись {у, Ь, х). Смешанные графы представляют собой совокупность ориентированных и неориентированных ветвей. Неориентированные и смещанные графы электронных Ц€1?ей, как правило, ненормированные. Для анализа микроэлсктроняых иепей обычно используют ори» ентированяые и смешанные графы, так как неориентированные графы как правило, применяются только для анализа чисто пассивных иепей а они в интегральных микросхемах отсутствуют [4, 25, 27. 4 68 711-74, 76-81, 88-90, 93-100]. Применительно к электронике графы еще классифицируются иа У- и К-трафы. Для построения У-1рафа используется метод узлсжых потенциалов, а для /(-графа-метод контурных токов. Очевидно, что оба эти графа, так же как и эти методы, дуальны. Однако на практике значительно чаще используют У-граф. Это объясняется его большей топологической идштичностью с анализируемой цепью, а следовательно, простотой его построения и наглядностью расчета. Поэтому во всех дальнейших рассуждениях под термином граф будет фигурировать только У-граф. Следует заметить, что ориентированные У-графы электронных цепей еще называют сигнальными. Это вызвано тем, что они наглядно иллюстрируют прохождение сигналов по цепи и весьма удобны при анализе сложных многоструктурных устройств с многопетлевыми обратными связями (скажем, аналоговых микросхем). Сигнальный анализ микросхемы удобцо проводить, представляя отдельные подсхемы в виде самостоятельных структур (миогополюоников), имеющих общую точку. Нередко некоторыми параметрами этих структур можно пренебречь (скажем, входными и выходными сопротивлениями). Это позволяет значительно упростить процедуру анализа. При этом анализируемое устройство описывается приближенно, что для исследований на уровне структур вполне допустимо [55]. Если требуется более детальный анализ цепи, то удобнее использовать смешанные или. как их еще называют, унисторные графы. В этом случае пассивная часть анализируемой цепя описывается неориентированным графом, а активная - с помощью унисторных моделей. Но, поскольку всякую неориентированную ветвь графа электронной цепи можо представить двумя равными и противоположно «аправлеяными унисторами, общий граф получил название унисторного. На основании вышеизложенного все дальнейшие рассуждения будут относиться только к упомянутым двум видам гра-фсз (сигнальным и унисторным). Дадим определения основных элементов графа. Цепь графа - это конечная или бесконечная последовательность ветвей графа, в которой каждые предыдущая и последующая ветви являются смежными. Если все ветви цепи различны, то ее называют простой, в противном случае - составной (сложной). Когда для любой пары узлов графа существует хотя бы одна соединяющая их цепь, такой граф называется связным. Все рассматриваемые в теории электронных цепей графы- связные. Циклом графа называется его конечная цепь, начинающаяся и кончающаяся на одном и том же узле. Цикл называется простым, если все его ветви различны, и составным, если он проходит по одной и той же [ 0 ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |