Полупроводниковые микросхемы. Многокристальная и однокристальная микросхема. Гибридно-плёночные микросхемы, страница 10

·  13. Характеристические числа графов

Цикломатическое число V(G) – число ребер, которое необходимо удалить из графа, чтобы он стал деревом.

R = |U| - число ребер графа. |T| = n-1                 V(G) =  R –  n + 1

Хроматическое числоR(G) – наименьшее число непересекающихся подмножеств вершин, на которые можно разбить число вершин тем образом, чтобы ребра графа соединяли только вершины разных подмножеств.

Граф называется плоским, если он расположен на плоскости тем образом, что ребра имеют общие точки лишь в вершинах.

Граф, изоморфный плоскому и имеющий пересечения ребер, называется планарным  (то есть его можно изобразить плоско).

Планарность графа определяется на основе нескольких критериев:

Операцией расширения графа называется замена одного ребра на два с дополнением вершины.

Сжатие – обратное расширению.

Исходный граф и расширенный (сжатый) не изоморфный до вершин второй степени графа  называется геоморфными, если  после сжатия (расширения) они становятся изоморфными. Граф геоморфный плоскому называется планарным. Теорема Понтягина – Куратковского Граф планарен тогда и только тогда, если он не содержит подграфов, геоморфных полному графу к5 и полному двудольному к3,3. к5 и к3,3 называются графами Понтягина – Куратковского Число планарности Q(G) – минимальное количество ребер, которые необходимо удалить из графа, чтобы он был планарным. Одной из основных гипотез теории графов является гипотеза о четырех красках. Любой планарный граф можно раскрасить не более чем в 4 краски.

Внутренне устойчивым множеством называется такое множество, что любые две вершины в нем не смежные.

Числом внутренней устойчивости α(G) называется величина, равная максимальной мощности Xs. α(G) = max | Xs |  Внешне устойчивым графом называется множество вершин Xs, выбранное таким образом, что для каждой вершины Xj не принадлежащей Xs существует вершина Xi принадлежащая Xs, связанная с X5. . Число внешней устойчивости

{x6, x4, x1} или {x6, x4, x2}

{x7, x8, x6} , следовательно

14. Планарность графов

Граф называется плоским, если он расположен на плоскости таким образом, что ребра имеют общие точки лишь в вершинах графа. Граф, изоморфный плоскому и имеющий пересечения ребер, называется планарным. Операцией расширения графа называется замена одного ребра на два с дополнением вершины. Сжатие – обратно расширению. Исходный граф и расширенный (или сжатый), изоморфный до вершин второй степени. Два графа называются гомеоморфными, если после сжатия (или расширения) они становятся изоморфными. Граф, гомеоморфный плоскому  также является планарным.

2 графа называются изоморфными, если у них одинаковое количество вершин и если каждой паре вершин, соединенных в одном графе соответствует пара вершин, соединенных ребром в другом графе.

Теорема Понтрягина - Куратовского:

Граф планарен тогда и только тогда, если он не содержит подграфов, гомеоморфных полному графу К5 и полному двудольному К3,3.

К5, К3,3 – графы Понтрягина – Куратовского.

Минимальное количество ребер, которое необходимо удалить из графа, чтоб он был планарным, называется числом планарности Q(G). Q(K_n) = (n-3)*(n-4)/2.

Одной из основных гипотез теории графов является гипотеза о 4^х красках: любой планарный граф можно раскрасить не более чем в 4 краски.

Планаризация графа

При проектировании однослойных структур или структур, у которых слои используются неодинаково, метрические методы не используются. А используется графотеоретический подход к синтезу топологии.

1.  построение графовой модели схемы.

2.  анализ планарности графа планаризация графа реализация непланарных соединений

3.  построение плоского чертежа схемы

4.  синтез геометрии схемы.