3 3 .Планарность графа, теорема Эйлера о многогранниках.
Граф наз. плоским, если его ребра не пересекаются.
Граф наз. планарным, если он изоморфен плоскому графу.
Граф G1 = (V1, E1) наз. изоморфным графу G2 = (V2, E2), если существует биекция f: V1→V2 такая, что для любых вершин х, уєV1 число ребер из Е1, инцидентных этим вершинам, равно числу ребер из Е2, инцидентных вершинам f(x) и f(у).
Ex: Графы G1 и G2 изоморфны.
Плоские графы
Ех: Планарные графы
Ех: Не планарные графы
Граф G укладывается на поверхности S, если G можно изобразить на S без пересечения ребер.
Теорема: Граф укладывается на сфере тогда и только тогда, когда он планарен.
Д ок-во: Предположим, что граф G уложен на сфере S. Выберем на сфере точку N, которая не лежит ни на одном ребре графа и не совпадает с вершиной. В точке сферы, противоположной точке N, проведем касательную плоскость π. Из точки N спроектируем сферу S без точки N на плоскость π. Обозначим образ графа G через G′. Т.к. проекция явл. биекцией сферы S|{N} на плоскость π, граф G′ явл. плоским и изоморфным исходному графу G -» G - планарный граф.
Гранями плоского графа наз. мax связанные обл-ти плоскости, на которые пл-ть делится ребрами графа
Р1 = {a1,a3,a2,a4} и соединяющие их ребра.
Р2 = {a3, a4, a5, a6} и соединяющие их ребра.
Теорема:Для любого связного графа число вершин n, число ребер m, число граней r связаны соотношением: n – m + r = 2 (*)
Док-во: Пусть G – связный плоский граф, т.е. состоящий из одной компоненты связности. Предположим, что G не имеет циклов, значит G явл. деревом, т.е. обыкновенным связным граф без циклов.) => n = m + 1 и r = 1 => n – m + r = m+1-m+1 = 2.
Предположим, что граф G содержит циклы. Рассмотрим ребро е, принадлежащее циклу => ребро е не явл. мостом и принадлежит двум граням р1 и р2, одну из которых можно считать внешней. Рассмотрим граф G′ = G – е. Граф G′ - связный и плоский (по теореме: если в связном графе удалить ребро, принадлежащее циклу, то граф останется связным). При удалении ребра е грани р1 и р2 сольются в одну внешнюю грань графа G′. Остальные грани останутся без изменения => граф G′ содержит на одно ребро и одну грань меньше, чем граф G. Т.к. число вершин этих графов совпадает, то выполняется равенство:
n ′ - m′ + r′ = n – m + r => при удалении ребра левая часть рав-ва (*) не меняется. Но разрывая циклы, получаем дерево, для которого (ранее доказано) выполняется рав-во (*) => для исходного графа рав-во (*) верно.
Следствие 1: Для плоского графа, имеющего С компонент связности, выполняется рав-во: n – m + r = 1 + c
Следствие 2: Граф К5 не планарен.
Следствие 3: Граф К3,3 не планарен.
- 1. Множества, булевы операции над множествами, основные их свойства.
- Булевы операции над множествами.
- 35. Разработка и оформление основных проектных документов (генплан).
- 2 2 . Граф, маршруты в графе, компоненты связности, связные графы.
- 36. Разработка и оформление основных проектных документов (планы зданий).
- 3 3 .Планарность графа, теорема Эйлера о многогранниках.
- 37.Разработка и оформление основных проектных документов (разрезы зданий).
- 4. Решение систем линейных уравнений методом Гаусса.
- 38.Разработка и оформление основных проектных документов (фасады зданий).
- Чертежи фасадов зданий.
- На фасады наносят:
- 5 5 .Матрицы, операции над матрицами, обратная матрица.
- Операции:
- 1) Сложение двух матриц
- 2) Умножением матрицы на число
- 3) Умножение двух матриц
- 39.На каких этапах архитектурного проектирования применяются пакеты компьютерной графики и какие?
- 6. Архитектура сетей. Топология и типология сетей. Одноранговые сети, сети на основе сервера, локальные и глобальные сети.
- Классификация
- Основные топологии локальных систем
- 40.Какие графические пакеты применяют при проектировании интерьеров и какие задачи они решают?
- 7 7 . Виды сервисов в Интернет.
- Основные сервисы Internet:
- 46.Социально-экологические проблемы города.
- 8 8 .Определение, назначение, состав и функции операционных систем.
- 47.Инженерное оборудование зданий.
- 9 9 .Классификация современных операционных систем.
- IV. Вытесняющая и невытесняющая многозадачность
- VII. Особенности областей использования:
- 48.Автоматизированные системы управления в современном здании, характеристика инженерных подсистем
- 10.Понятие информационной технологии. Эволюция информационных технологий.
- Эволюция информационных технологий.
- 49.Типологические особенности архитектуры городов.
- 1 11 1.Информационная система как средство реализации информационной технологии.
- 33.Средства архитектурной композиции (тектоника, ритм, симметрия, контраст, нюанс и др.).
- Художественные средства архитектуры
- 12.Понятие и свойства базы данных. Требования, предъявляемые к бд.
- 34.Стадийность архитектурного проектирования.
- 1 13 3.Система управления бд. Основные компоненты и функции субд.
- 50.Градостроительство–деятельность человека по преобразованию природной среды. Виды градостроительной деятельности.
- 14.Иерархическая, сетевая и реляционная модели представления данных. Достоинства и недостатки различных моделей.
- 51.Уровни градостроительного проектирования. Градостроительная документация.
- 1 15 5.Угрозы информационной безопасности, причины виды и каналы утечки информации
- 52.Типология населённых мест по величине, народнохозяйственному профилю, географическому положению.
- 1 16 6.Методы защиты информации в компьютерных системах
- 53.Функциональное зонирование города. Типы функционального зонирования.
- 8 Зон делятся на 3 группы:
- 1 17 7. Объекты и основные задачи информационного менеджмента.
- 41.Задачи экономической работы при проектировании городов.
- 1 18 8. Информационный менеджмент как новый тип управления учреждением.
- 42.Права и обязанности лица, осуществляющего архитектурную деятельность.
- Гл.III. Ст.12. Архитектор и юридическое лицо, имеющие лицензии, на основании договора с заказчиком (застройщиком) имеют право:
- 1 19 9.Понятие, свойства и характеристики алгоритмов.
- 43.Государственная экспертиза проектной документации: цели и задачи, этапы
- 2 20 0.Виды языков программирования.
- 44.Влияние деятельности человека на равновесие природных систем.
- 2 21 1. Понятие объектно-ориентированного подхода. Классы как пользовательские типы данных. Объекты как экземпляры классов.
- 45.Архитектурное проектирование – выбор оптимального варианта проектного решения, несущего социально-экологический комфорт.
- 2 22 2.Принципы объектно-ориентированного программирования. Наследование и агрегирование как способы создания новых классов.
- 32.Архитектура как вид искусства. Эстетический, средовой, культурологический подходы к архитектуре.
- 3. Архитектурная среда как возможность
- 2 23 3. Программирование в оконных операционных средах. Интегрированные среды разработки. Визуальное программирование.
- 54.Планировочная структура населенного места. Типы планировочных структур населенных мест.
- 24.Жизненный цикл ис. Состав работ на всех стадиях жизненного цикла ис
- 62.Основные задачи ландшафтного проектирования. Элементы ландшафтной системы. Классификация ландшафтов.
- 2 25 5.Автоматизированное проектирование ис с использованием case-технологии.
- 61. Критерии оптимальности планировочной структуры градостроительной системы.
- 2 26 6. Содержание rad-технологии создания приложений.
- 60.Реконструкция населённых мест. Цели, задачи, виды реконструкции.
- 27.Понятие и составляющие качества программного средства.
- 59.Транспортная структура как основной планировочный каркас города. Типы транспортных структур.
- 2 28 8. Разработка структуры программы и модульное программирование.
- Методы разработки структуры программы
- 58.Система озеленения населенных мест. Типы и виды озеленённых территорий города.
- Система озеленения состоит из 3-х элементов или категорий:
- Виды озелененных территорий города:
- 2 29 9.Тестирование и отладка программного средства.
- 57.Центр города. Типология планировочных структур.
- 3 30 0.Понятие проектирования. Стадии и этапы проектирования. Содержание работ на различных стадиях.
- Стадии и этапы проектирования
- 56.Пром. Зона, пром. Район, пром. Узел. Основные характеристики.
- 3 31 1.Состав и структура сапр. Виды обеспечения сапр.
- Виды обеспечения сапр
- 55.Особенности организации жилых образований поселений.