Эйлеровы и полуэйлеровы графы

Именно с задач, поставленных и решенных в этом разделе, началась теория графов. Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах:можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. Наш петербургский знаменитый математик швейцарского происхождения Леонард Эйлер блестяще решил эту задачу. На рис. 2 изображена схема семи мостов Кенигсберга (заметим, что сейчас осталось только два из них), а также мультиграф, соответствующий этой схеме (при построении графа считалось, что каждый берег реки и острова – это вершины графа, а мосты – его ребра; видно, что в данном случае у нас получился мультиграф без петель).

В соответствии с поставленной Кантом (и решенной Эйлером) задачей можно дать следующие определения:

Граф (или мультиграф без петель) называется эйлеровым, если существует цикл без повторения ребер (такой цикл называют эйлеровым),обходящий все вершины графа. Граф называется полуэйлеровым,если существует маршрут без повторения ребер (эйлеров путь), обходящий все ребра графа ровно один раз. На рис. 3 изображены: а – эйлеров граф, б – полуэйлеров граф и в – граф, не являющийся ни эйлеровым, ни полуэйлеровым (люди старшего поколения знают, что в школах раньше было много загадок типа “можно ли нарисовать данную фигуру не отрывая ручку от бумаги”, что и соответствует эйлерову или полуэйлерову графу).

Теорема (Эйлер). Для того чтобы данный связный граф (не орграф, но, возможно, мультиграф без петель) был эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четными.Данный связный граф будет полуэйлеровым тогда и только тогда, когда степени двух вершин будут нечетными, а степени остальных вершин – четными.

Доказательство этой теоремы начнем с так называемой леммы о рукопожатиях. Название этой леммы связано с тем, что эта лемма отвечает на следующий вопрос: У Вас собрались гости. Некоторые из них здороваются друг с другом посредством рукопожатий. Какими свойствами обладает число таких людей? Ответ дается следующей достаточно простой леммой.

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

Доказательство леммы. Заметим, что сумма степеней всех вершин в графе (или мультиграфе без петель) должна быть четной. Это следует из того, что если взять вершины, вообще не связанные друг с другом, то сумма степеней этих вершин равна нулю. Прибавляя любое ребро, которое связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна. Удаляя из этой суммы степени четных вершин, получим, что сумма степеней нечетных вершин, должна быть четной. Это значит, что само число таких вершин должно быть четным. Лемма доказана.

С точки зрения задачи о рукопожатиях это означает, что число гостей, которые поздоровались за руку нечетное число раз, должно быть четным.Перейдем к доказательству теоремы Эйлера.

А) Пусть граф является эйлеровым. Тогда в нем имеется эйлеров цикл, который должен прийти в вершину по одному ребру и покинуть его по другому, так как каждое ребро должно использоваться только один раз (т. е. каждый “заход” в вершину и “выход” из нее дает 2 степени вершины). Таким образом, сумма степеней всех вершин должна быть четной (и равна удвоенному числу “заходов” в эту вершину при обходе эйлерова цикла).

Б) Пусть в данном связном графе (или мультиграфе без петель) степень любой вершины четна (т. е. степень больше или равна 2, так как нулевая степень приводит к несвязному графу). Докажем, что в нем имеется эйлеров цикл. Доказательство проведем индукцией по числу вершин. В случае, когда в связном графе всего 2 вершины и обе они имеют четную степень (в этом случае имеем мультиграф, один из которых изображен на рис. 4), ясно, что в этом случае имеется эйлеров цикл (при любой четной степени этих двух вершин).

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

Заметим, что по лемме 1 в этом графе есть контур (степень всех вершин больше или равна 2). Если этот контур содержит все ребра, то этот контур сам является эйлеровым циклом (а граф эйлеровым). Удалим все эти ребра из графа и те вершины, которые после удаления ребер стали иметь нулевую степень. Тогда получим новый граф (который может быть несвязным), но в этом новом графе все вершины обязательно имеют четную степень (так как при удалении ребер контура степень каждой вершины, входящей в этот контур, уменьшается на 2). Новый граф распадается на “ компоненты связности ”,каждая из которых должна иметь общую вершину с удаленным контуром (иначе первоначальный граф не был бы связным), степени всех вершин каждой компоненты связности четны и число вершин в ней строго меньше п,т. е. по индукционному предположению эта компонента имеет эйлеров цикл. Теперь можем построить эйлеров цикл в данном графе следующим образом. Обходим последовательно ребра удаленного контура. Если мы пришли в вершину, общую для контура и какой-то компоненты связности, то обходим по эйлерову циклу эту компоненту, возвращаемся при этом в вершину контура и идем по этому контуру дальше. Тем самым все ребра будут пройдены и каждое только один раз (все это схематично изображено на рис. 5: сначала начинаем обходить контур АВСDEА. Пройдя ребро АВ, проходим “верхний” граф, затем возвращаемся в т. В и далее идем по ребру АС, обходим “правый” граф и т. д.). Утверждение Б доказано.

В) Пусть теперь граф полуэйлеров. Это значит, что он имеет эйлеров путь, начинающийся в одной вершине и заканчивающийся в другой. Видно, что обе эти вершины должны иметь нечетную степень, а степень остальных четная.

Г) Обратно. Пусть в связном графе вершины к и р имеют нечетную степень, а остальные вершины – четную. Тогда возможны 2 случая: эти вершины связаны ребром или не связаны. В первом случае удалим это ребро, а во втором добавим. В обоих случаях степень всех вершин станет четной. Заметим, что в случае удаления ребра, новый граф может стать несвязным и иметь 2 компоненты связности (в этом случае удаляемое ребро было мостом), каждая из которых или весь новый граф имеет эйлеров цикл. Теперь если новый граф имеет эйлеров цикл, то начнем (и закончим его) в вершине с нечетной степенью и далее добавим ребро или удалим его. В обоих случаях получим эйлеров путь. Если новый граф имеет 2 компоненты связности, то, пройдя одну из них по эйлерову циклу, начиная и заканчивая в вершине (которая в первоначальном графе имела нечетную степень), затем добавим удаленное ребро (мост), пройдем его, попадем в другую вершину, которая ранее имела нечетную степень, и пройдем вторую компоненту связности по эйлерову циклу. Во всех разобранных случаях получим эйлеров путь, который начался в одной из вершин с нечетной степенью и закончился в другой. Теорема доказана.

Заметим, что все 4 вершины мультиграфа (рис. 2), соответствующего мостам Кенигсберга, имеют степень 3. Поэтому эйлеров цикл или путь невозможен.

Примечание. Еслиграф (или мультиграф без петель) содержит 2 k вершин нечетной степени, то его можно разбить на k полуэйлеровых графов (т. е. нарисовать k росчерками пера). Доказательство аналогично доказательству теоремы Эйлера.

Имеется простой алгоритм(так называемый алгоритм Флери) для нахождения эйлерова цикла (конечно, если этот цикл существует), который состоит в следующем: начинаем с любой вершины и “ стираем ” пройденные ребра. При этом по мосту (перешейку) проходим только, если нет других возможностей.

Очевидно, что для того чтобы построить эйлеров путьдостаточно использовать алгоритм Флери, который надо начать с вершины, имеющей нечетную степень.

Рассмотримнекоторые приложения теоремы Эйлера, которые в основном связаны с так называемой задачей китайского почтальона.

Пусть имеется некоторый граф (связный), ребрам которого приписаны некоторые числа, называемые весами ребер (часто, но не всегда!, в приложениях вес ребра – это его длина).Требуется найти такой цикл, при котором каждое ребро проходится по крайней мере один раз и суммарный вес всех ребер, вошедших в цикл, минимален. Заметим, что если граф является эйлеровым, то любой эйлеров цикл решает поставленную задачу (для эйлерова графа веса роли не играют).

Эта задача имеет много приложений, например, поливка улиц одной машиной (здесь ребра графа – дороги, а перекрестки – вершины; веса – это длины дорог), а также сбор мусора, доставка почты или даже наилучший маршрут для осмотра музея или уборка помещений и коридоров в больших учреждениях.

Заметим, что имеется алгоритм решения задачи китайского почтальона, но он требует достаточно длительного описания.

Кратко рассмотрим проблему, связанную с возможным обходом всех вершин в графе: существует ли в данном (связном) графе цикл (или маршрут), обходящий каждую вершину (кроме первой) только один раз. Если такой цикл (маршрут) существует (в этом случае такой цикл будет контуром, а маршрут – путем), то граф называется гамильтоновым (полугамильтоновым),и соответствующий цикл (путь) также называют гамильтоновым циклом (путем).

На рис. 6 изображены гамильтонов, полугамильтонов и не гамильтонов графы.

Несмотря на сходство постановки задач для гамильтоновых графов с эйлеровыми, “хорошего” решения для гамильтоновых графов нет. Вообще, о гамильтоновых графах известно очень мало. В основном – это теоремы типа “если в графе достаточное число ребер, то он гамильтонов”. Ясно, что теоремы такого типа не могут дать критерия гамильтонова графа, (рис. 6,а), поскольку в графах такого типа вершин может быть очень много, а ребер сравнительно мало).

Приведем без доказательства самую известную теорему.

Теорема (Дирак, 1952). Если в связном графе с п вершинами (при n ³3 ) степени всех вершин больше или равны п/ 2, то граф гамильтонов.

11. Матрицы и графы. Нахождение путей и сечений
с помощью структурной матрицы

Трудно переоценить роль матриц в теории графов (в частности, матрицы полезны, чтобы данный граф более “легко” воспринимался компьютером). Перечислим наиболее известные матрицы.

1. Матрица смежности. Это квадратная матрица порядка п (п – число вершин), в которой нули стоят по главной диагонали (если в графе нет петель, а если петли есть в вершине k (и число этих петель равно р),то на главной диагонали в строчке с номером k стоит число р). Если вершина i связана с вершиной j однимребром, то элемент матрицы смежности a_ij равен 1, если эти вершинысвязаны s ребрами, то а_ij= s. Аналогичным образом строятся матрицы смежности для орграфов и для мультиграфов.

Легко видеть, что матрица В =А ² = АА составлена из целых чисел b_ij,которые равны числу путей длины 2, соединяющих вершины i и j. Понятно, что А ³составлена из чисел, равных числу путей длины 3 (т. е. путей из 3-х ребер) из вершины i ввершину j и т. д.

1. Матрица инциденций – это матрица размера n ´ m,где n – число вершин, а m – число ребер графа, при этом ее элементы k_ij равны 1, если вершина с номером i является для ребра с номером j начальной или конечной (если ребро неориентировано) и начальной для ориентированных ребер. Заметим, что матрица инциденций сравнительно редко используется, так как в современных условиях (где число ребер часто очень велико) она имеет слишком большое число столбцов.
2. Структурная матрица. Именно эта матрица имеет особое значение в теории сетей связи. Структурная матрица – это символьная матрица порядка п. Она составляется следующим образом: на главной диагонали стоит 1, т. е. a_ii = 1, остальные элементы – это символьные обозначения ребер (если вершины i и j не соединены ребром, то a_ii = 0). При этом, если при i < j вершины i и j соединены ребром а, то элемент s_ij = a,при i>j – это отрицание а, которое обычно отмечается чертой сверху. Если связи вершины i c вершиной j нет, то соответствующий элемент равен 0, структурная матрица может составляться и для орграфа и для мультиграфа без петель (здесь если дваребра а и b соединяют две вершины, то соответствующий элемент при i <j равен a Ú b,апри i>j этот элемент равен

Отметим, что в учебных целях, когда действия с матрицами осуществляются студентами “вручную” (число вершин в графе невелико), можно обозначать ребра латинскими буквами без индексов a, b, c и т. д., но при использовании компьютера гораздо удобнее обозначать ребра а (i,j), если это ребро соединяет вершины i и j при i<j и с чертой сверху, если i>j.

Теорема. Для того чтобы найти все пути (простые) из вершины i в вершину j достаточно раскрыть минор M (j, i) структурной матрицы методами булевой алгебры. При этом раскрытие минора производится обычными действиями с определителями, но при этом сложение заменяется дизъюнкцией, умножение – конъюнкцией, знаки умножения на числа не используются.

Подробно доказывать эту теорему не будем, но отметим, что определитель равен сумме (в данном случае дизъюнкции) элементов, взятых по одному из каждой строчки и каждого столбца с определенным знаком. В нашем случае знаки не присутствуют, а значит, любой член раскрытия определителя всей структурной матрицы S соответствует циклу в графе. Если же брать минор M (j,i),то его раскрытие соответствует тем членам определителя, в которых имелся элемент s (j,i),но безсамого этого элемента (таким образом, индексы i и j встречаютсявместо двух только один раз). Это и означает, что получаем маршрут от вершины с номером i к вершине с номером j.

Понятно, что раскрытие минора методами булевой алгебры предусматривает, что верны следующие соотношения: 1Ú a = 1, (это свойство нужно, для того чтобы не проходить по одному ребру дважды в противоположных направлениях), а также используется правило простого поглощения (х Ú ху = х). Видно, что если не использовать правило поглощения, то получим все маршруты (без повторения ребер), связывающие вершины i и j.

Примечание. 1. Если граф не ориентирован, то миноры M (j,i)и M(i,j) совпадают.

2. После получения ответа, черточки над обозначениями ребер (т. е. отрицания) можно убрать (на самом деле “черта” над ребром означает, что ребро проходится от вершины с большим номером к вершине с меньшим номером). Затем рекомендуется записать каждый путь по порядку прохождения ребер (в этом случае удобны обозначения ребер с индексами вершин).

Сечением (разрезом) междувершинами i и j называется неизбыточный набор ребер, при удалении которых из графа теряется связь между данными вершинами (не существует пути из вершины i в вершину j). Заметим, что сечений между данными вершинами может быть много, и они могут содержать разное количество ребер.

Слово “неизбыточный” означает, что если любое ребро из сечения снова возвратить в граф, то связь восстановится.

Естественно, что если известны все пути из вершины i в вершину j, причем эти пути заданы в виде ДНФ, т. е. дизъюнктивной нормальной формы (а именно такой вид получается после раскрытия соответствующего минора структурной матрицы), то все сечения между этими вершинами можно получить отрицанием этих путей (по правилу де Моргана конъюнкцию заменить на дизъюнкцию и наоборот), затем полученное выражение снова привести к ДНФ, используя раскрытие скобок по обычным правилам, при этом правило поглощения обеспечит неизбыточность набора ребер в каждом сечении. Ясно, что знаки отрицания (черточки над символами ребер) можно опустить. Пример на эту тему приведен в разд. 15 (примеры решения типовых задач).

Варианты контрольной работы MPSetChAttrs('ch0042','ch4',[[13,10,0,0,-1],[17,12,0,0,-1],[22,15,0,0,-1],[],[],[],[56,41,1,0,-2]]) MPInlineChar(0) 1

Вариант 1

1. Выполнить действия MPSetEqnAttrs('eq0776','',3,[[57,12,0,-1,-1],[75,16,0,-1,-1],[93,19,0,-1,-1],[],[],[],[231,49,1,-3,-3]]) MPEquation() , где

MPSetEqnAttrs('eq0776','',3,[[57,12,0,-1,-1],[75,16,0,-1,-1],[93,19,0,-1,-1],[],[],[],[231,49,1,-3,-3]]); MPSetEqnAttrs('eq0777','',3,[[82,37,15,-1,-1],[110,50,21,-1,-1],[136,61,25,-1,-1],[],[],[],[342,154,63,-3,-3]]) MPEquation() MPSetEqnAttrs('eq0778','',3,[[94,37,15,-1,-1],[124,50,21,-1,-1],[155,61,25,-1,-1],[],[],[],[391,154,63,-3,-3]]) MPEquation() MPSetEqnAttrs('eq0779','',3,[[101,37,15,-1,-1],[135,50,21,-1,-1],[169,61,25,-1,-1],[],[],[],[423,154,63,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0779','',3,[[101,37,15,-1,-1],[135,50,21,-1,-1],[169,61,25,-1,-1],[],[],[],[423,154,63,-3,-3]]); MPSetEqnAttrs('eq0778','',3,[[94,37,15,-1,-1],[124,50,21,-1,-1],[155,61,25,-1,-1],[],[],[],[391,154,63,-3,-3]]); MPSetEqnAttrs('eq0777','',3,[[82,37,15,-1,-1],[110,50,21,-1,-1],[136,61,25,-1,-1],[],[],[],[342,154,63,-3,-3]]);

2. Решить систему уравнений

MPSetEqnAttrs('eq0780','',3,[[104,59,26,-1,-1],[138,78,34,-1,-1],[171,98,44,-1,-1],[],[],[],[431,244,108,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0780','',3,[[104,59,26,-1,-1],[138,78,34,-1,-1],[171,98,44,-1,-1],[],[],[],[431,244,108,-3,-3]]);

3. Найти работу вектора MPSetEqnAttrs('eq0781','',3,[[61,12,0,-1,-1],[80,16,0,-1,-1],[101,20,0,-1,-1],[],[],[],[255,51,0,-3,-3]]) MPEquation() вдоль вектора MPSetEqnAttrs('eq0782','',3,[[58,12,0,-1,-1],[77,16,0,-1,-1],[97,20,0,-1,-1],[],[],[],[245,52,1,-3,-3]]) MPEquation() , если MPSetEqnAttrs('eq0783','',3,[[35,13,3,-1,-1],[47,17,4,-1,-1],[59,21,5,-1,-1],[],[],[],[146,53,12,-3,-3]]) MPEquation() ,

MPSetEqnAttrs('eq0783','',3,[[35,13,3,-1,-1],[47,17,4,-1,-1],[59,21,5,-1,-1],[],[],[],[146,53,12,-3,-3]]); MPSetEqnAttrs('eq0782','',3,[[58,12,0,-1,-1],[77,16,0,-1,-1],[97,20,0,-1,-1],[],[],[],[245,52,1,-3,-3]]); MPSetEqnAttrs('eq0781','',3,[[61,12,0,-1,-1],[80,16,0,-1,-1],[101,20,0,-1,-1],[],[],[],[255,51,0,-3,-3]]); MPSetEqnAttrs('eq0784','',3,[[33,15,3,-1,-1],[44,20,4,-1,-1],[54,25,5,-1,-1],[],[],[],[138,64,13,-3,-3]]) MPEquation() и MPSetEqnAttrs('eq0785','',3,[[55,29,11,-1,-1],[73,39,14,-1,-1],[91,48,18,-1,-1],[],[],[],[232,120,45,-3,-3]]) MPEquation() .

MPSetEqnAttrs('eq0785','',3,[[55,29,11,-1,-1],[73,39,14,-1,-1],[91,48,18,-1,-1],[],[],[],[232,120,45,-3,-3]]); MPSetEqnAttrs('eq0784','',3,[[33,15,3,-1,-1],[44,20,4,-1,-1],[54,25,5,-1,-1],[],[],[],[138,64,13,-3,-3]]); 4. Найти большую высоту параллелограмма, построенного на векторах

MPSetEqnAttrs('eq0786','',3,[[72,13,3,-1,-1],[95,17,4,-1,-1],[118,21,5,-1,-1],[],[],[],[296,54,13,-3,-3]]) MPEquation() и MPSetEqnAttrs('eq0787','',3,[[67,15,3,-1,-1],[90,20,4,-1,-1],[112,25,5,-1,-1],[],[],[],[281,64,13,-3,-3]]) MPEquation() , как на сторонах.

MPSetEqnAttrs('eq0787','',3,[[67,15,3,-1,-1],[90,20,4,-1,-1],[112,25,5,-1,-1],[],[],[],[281,64,13,-3,-3]]); MPSetEqnAttrs('eq0786','',3,[[72,13,3,-1,-1],[95,17,4,-1,-1],[118,21,5,-1,-1],[],[],[],[296,54,13,-3,-3]]); 5. Точки MPSetEqnAttrs('eq0788','',3,[[240,13,3,-1,-1],[319,17,4,-1,-1],[399,21,5,-1,-1],[],[],[],[997,54,13,-3,-3]]) MPEquation() лежат в одной плоскости. Найти абсциссу точки С.

MPSetEqnAttrs('eq0788','',3,[[240,13,3,-1,-1],[319,17,4,-1,-1],[399,21,5,-1,-1],[],[],[],[997,54,13,-3,-3]]); Ответы:

1. MPSetEqnAttrs('eq0789','',3,[[86,37,15,-1,-1],[114,50,21,-1,-1],[144,61,25,-1,-1],[],[],[],[359,154,63,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0789','',3,[[86,37,15,-1,-1],[114,50,21,-1,-1],[144,61,25,-1,-1],[],[],[],[359,154,63,-3,-3]]);

2. Система имеет бесчисленное множество решений

MPSetEqnAttrs('eq0790','',3,[[257,13,3,-1,-1],[346,17,4,-1,-1],[432,21,5,-1,-1],[],[],[],[1079,54,13,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0790','',3,[[257,13,3,-1,-1],[346,17,4,-1,-1],[432,21,5,-1,-1],[],[],[],[1079,54,13,-3,-3]]); 3. MPSetEqnAttrs('eq0791','',3,[[74,16,2,-1,-1],[99,21,2,-1,-1],[123,26,3,-1,-1],[],[],[],[307,63,6,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0791','',3,[[74,16,2,-1,-1],[99,21,2,-1,-1],[123,26,3,-1,-1],[],[],[],[307,63,6,-3,-3]]); 4. h = 5.

5. x = -1.

Вариант 2

1. Решить матричное уравнение MPSetEqnAttrs('eq0792','',3,[[131,37,15,-1,-1],[174,50,21,-1,-1],[219,61,25,-1,-1],[],[],[],[547,154,63,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0792','',3,[[131,37,15,-1,-1],[174,50,21,-1,-1],[219,61,25,-1,-1],[],[],[],[547,154,63,-3,-3]]); 2. Решить систему матричным способом

MPSetEqnAttrs('eq0793','',3,[[104,59,26,-1,-1],[139,78,34,-1,-1],[172,98,44,-1,-1],[],[],[],[432,244,108,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0793','',3,[[104,59,26,-1,-1],[139,78,34,-1,-1],[172,98,44,-1,-1],[],[],[],[432,244,108,-3,-3]]);

3. Даны три вектора

MPSetEqnAttrs('eq0794','',3,[[312,15,3,-1,-1],[417,20,4,-1,-1],[521,25,5,-1,-1],[],[],[],[1302,64,13,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0794','',3,[[312,15,3,-1,-1],[417,20,4,-1,-1],[521,25,5,-1,-1],[],[],[],[1302,64,13,-3,-3]]); Вычислить 1) MPSetEqnAttrs('eq0795','',3,[[62,16,4,-1,-1],[82,21,5,-1,-1],[104,26,6,-1,-1],[],[],[],[258,66,15,-3,-3]]) MPEquation() ; 2) MPSetEqnAttrs('eq0796','',3,[[52,21,3,-1,-1],[70,29,4,-1,-1],[88,36,5,-1,-1],[],[],[],[220,89,13,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0796','',3,[[52,21,3,-1,-1],[70,29,4,-1,-1],[88,36,5,-1,-1],[],[],[],[220,89,13,-3,-3]]); MPSetEqnAttrs('eq0795','',3,[[62,16,4,-1,-1],[82,21,5,-1,-1],[104,26,6,-1,-1],[],[],[],[258,66,15,-3,-3]]);

4. Найти площадь треугольника, построенного на векторах MPSetEqnAttrs('eq0797','',3,[[57,12,0,-1,-1],[76,16,0,-1,-1],[94,20,0,-1,-1],[],[],[],[238,51,0,-3,-3]]) MPEquation() и

MPSetEqnAttrs('eq0797','',3,[[57,12,0,-1,-1],[76,16,0,-1,-1],[94,20,0,-1,-1],[],[],[],[238,51,0,-3,-3]]); MPSetEqnAttrs('eq0798','',3,[[59,12,0,-1,-1],[79,16,0,-1,-1],[98,20,0,-1,-1],[],[],[],[247,51,0,-3,-3]]) MPEquation() , если MPSetEqnAttrs('eq0799','',3,[[164,29,11,-1,-1],[219,39,14,-1,-1],[273,48,18,-1,-1],[],[],[],[683,120,45,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0799','',3,[[164,29,11,-1,-1],[219,39,14,-1,-1],[273,48,18,-1,-1],[],[],[],[683,120,45,-3,-3]]); MPSetEqnAttrs('eq0798','',3,[[59,12,0,-1,-1],[79,16,0,-1,-1],[98,20,0,-1,-1],[],[],[],[247,51,0,-3,-3]]); 5. Найти объем пирамиды с вершинами MPSetEqnAttrs('eq0800','',3,[[207,13,3,-1,-1],[277,17,4,-1,-1],[346,21,5,-1,-1],[],[],[],[865,54,13,-3,-3]]) MPEquation() и

MPSetEqnAttrs('eq0800','',3,[[207,13,3,-1,-1],[277,17,4,-1,-1],[346,21,5,-1,-1],[],[],[],[865,54,13,-3,-3]]); MPSetEqnAttrs('eq0801','',3,[[57,13,3,-1,-1],[76,17,4,-1,-1],[96,21,5,-1,-1],[],[],[],[241,54,13,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0801','',3,[[57,13,3,-1,-1],[76,17,4,-1,-1],[96,21,5,-1,-1],[],[],[],[241,54,13,-3,-3]]); Ответы:

1. X = MPSetEqnAttrs('eq0802','',3,[[62,53,23,-1,-1],[82,72,32,-1,-1],[104,90,39,-1,-1],[],[],[],[258,226,98,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0802','',3,[[62,53,23,-1,-1],[82,72,32,-1,-1],[104,90,39,-1,-1],[],[],[],[258,226,98,-3,-3]]);

2. x = -1, y = 2, z = 3.

3. MPSetEqnAttrs('eq0803','',3,[[233,33,14,-1,-1],[312,43,18,-1,-1],[388,54,23,-1,-1],[],[],[],[971,132,56,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0803','',3,[[233,33,14,-1,-1],[312,43,18,-1,-1],[388,54,23,-1,-1],[],[],[],[971,132,56,-3,-3]]); 4. MPSetEqnAttrs('eq0804','',3,[[63,33,11,-1,-1],[84,44,14,-1,-1],[106,57,19,-1,-1],[],[],[],[264,140,46,-3,-3]]) MPEquation()

MPSetEqnAttrs('eq0804','',3,[[63,33,11,-1,-1],[84,44,14,-1,-1],[106,57,19,-1,-1],[],[],[],[264,140,46,-3,-3]]); 5. MPSetEqnAttrs('eq0805','',3,[[44,16,6,-1,-1],[58,19,7,-1,-1],[75,24,9,-1,-1],[],[],[],[185,62,22,-3,-3]]) MPEquation()

Варианты контрольной работы № MPSetChAttrs('ch0083','ch4',[[13,10,0,0,-1],[17,12,0,0,-1],[22,15,0,0,-1],[],[],[],[56,41,1,0,-2]]) MPInlineChar(0) 2

MPSetChAttrs('ch0083','ch4',[[13,10,0,0,-1],[17,12,0,0,-1],[22,15,0,0,-1],[],[],[],[56,41,1,0,-2]])

Вариант 1

1. Даны вершины треугольника MPSetEqnAttrs('eq1539','',3,[[95,13,3,-1,-1],[126,17,4,-1,-1],[158,21,5,-1,-1],[],[],[],[395,54,13,-3,-3]]) MPEquation() и MPSetEqnAttrs('eq1540','',3,[[47,13,3,-1,-1],[62,17,4,-1,-1],[78,21,5,-1,-1],[],[],[],[195,54,13,-3,-3]]) MPEquation() . Составить уравнение медианы, проведенной из вершины В.

MPSetEqnAttrs('eq1540','',3,[[47,13,3,-1,-1],[62,17,4,-1,-1],[78,21,5,-1,-1],[],[],[],[195,54,13,-3,-3]]); MPSetEqnAttrs('eq1539','',3,[[95,13,3,-1,-1],[126,17,4,-1,-1],[158,21,5,-1,-1],[],[],[],[395,54,13,-3,-3]]); 2. Найти острый угол между прямой MPSetEqnAttrs('eq1541','',3,[[61,59,26,-1,-1],[81,78,34,-1,-1],[100,98,44,-1,-1],[],[],[],[254,244,108,-3,-3]]) MPEquation() и плоскостью MPSetEqnAttrs('eq1542','',3,[[72,10,0,-1,-1],[97,12,0,-1,-1],[121,15,0,-1,-1],[],[],[],[304,40,1,-3,-3]]) MPEquation() .

MPSetEqnAttrs('eq1542','',3,[[72,10,0,-1,-1],[97,12,0,-1,-1],[121,15,0,-1,-1],[],[],[],[304,40,1,-3,-3]]); MPSetEqnAttrs('eq1541','',3,[[61,59,26,-1,-1],[81,78,34,-1,-1],[100,98,44,-1,-1],[],[],[],[254,244,108,-3,-3]]); 3. Даны две точки MPSetEqnAttrs('eq1543','',3,[[66,14,4,-1,-1],[87,18,5,-1,-1],[109,22,6,-1,-1],[],[],[],[273,55,15,-3,-3]]) MPEquation() и MPSetEqnAttrs('eq1544','',3,[[60,14,4,-1,-1],[79,18,5,-1,-1],[100,22,6,-1,-1],[],[],[],[250,55,15,-3,-3]]) MPEquation() . Составить уравнение плоскости, проходящей через точку MPSetEqnAttrs('eq1545','',3,[[16,14,4,-1,-1],[21,17,5,-1,-1],[26,21,6,-1,-1],[],[],[],[69,53,15,-3,-3]]) MPEquation() перпендикулярно вектору MPSetEqnAttrs('eq1546','',3,[[35,17,4,-1,-1],[47,23,5,-1,-1],[59,29,7,-1,-1],[],[],[],[146,74,18,-3,-3]]) MPEquation() .

MPSetEqnAttrs('eq1546','',3,[[35,17,4,-1,-1],[47,23,5,-1,-1],[59,29,7,-1,-1],[],[],[],[146,74,18,-3,-3]]); MPSetEqnAttrs('eq1545','',3,[[16,14,4,-1,-1],[21,17,5,-1,-1],[26,21,6,-1,-1],[],[],[],[69,53,15,-3,-3]]); MPSetEqnAttrs('eq1544','',3,[[60,14,4,-1,-1],[79,18,5,-1,-1],[100,22,6,-1,-1],[],[],[],[250,55,15,-3,-3]]); MPSetEqnAttrs('eq1543','',3,[[66,14,4,-1,-1],[87,18,5,-1,-1],[109,22,6,-1,-1],[],[],[],[273,55,15,-3,-3]]); 4. Составить уравнение плоскости, проходящей через точку MPSetEqnAttrs('eq1547','',3,[[65,14,4,-1,-1],[86,18,5,-1,-1],[108,22,6,-1,-1],[],[],[],[270,55,15,-3,-3]]) MPEquation() , перпендикулярно двум плоскостям MPSetEqnAttrs('eq1548','',3,[[73,13,3,-1,-1],[99,16,4,-1,-1],[122,20,5,-1,-1],[],[],[],[308,52,12,-3,-3]]) MPEquation() и MPSetEqnAttrs('eq1549','',3,[[74,13,3,-1,-1],[99,16,4,-1,-1],[123,20,5,-1,-1],[],[],[],[308,52,12,-3,-3]]) MPEquation() .

MPSetEqnAttrs('eq1549','',3,[[74,13,3,-1,-1],[99,16,4,-1,-1],[123,20,5,-1,-1],[],[],[],[308,52,12,-3,-3]]); MPSetEqnAttrs('eq1548','',3,[[73,13,3,-1,-1],[99,16,4,-1,-1],[122,20,5,-1,-1],[],[],[],[308,52,12,-3,-3]]); MPSetEqnAttrs('eq1547','',3,[[65,14,4,-1,-1],[86,18,5,-1,-1],[108,22,6,-1,-1],[],[],[],[270,55,15,-3,-3]]); 5. Найти точку Q, симметричную точке MPSetEqnAttrs('eq1550','',3,[[66,13,3,-1,-1],[88,17,4,-1,-1],[110,21,5,-1,-1],[],[],[],[277,54,13,-3,-3]]) MPEquation() относительно плоскости MPSetEqnAttrs('eq1551','',3,[[86,13,3,-1,-1],[116,16,4,-1,-1],[144,20,5,-1,-1],[],[],[],[361,52,12,-3,-3]]) MPEquation() .

MPSetEqnAttrs('eq1551','',3,[[86,13,3,-1,-1],[116,16,4,-1,-1],[144,20,5,-1,-1],[],[],[],[361,52,12,-3,-3]]); MPSetEqnAttrs('eq1550','',3,[[66,13,3,-1,-1],[88,17,4,-1,-1],[110,21,5,-1,-1],[],[],[],[277,54,13,-3,-3]]); Ответы:

1. MPSetEqnAttrs('eq1552','',3,[[87,13,3,-1,-1],[117,16,4,-1,-1],[144,20,5,-1,-1],[],[],[],[362,52,12,-3,-3]]) MPEquation() ;

MPSetEqnAttrs('eq1552','',3,[[87,13,3,-1,-1],[117,16,4,-1,-1],[144,20,5,-1,-1],[],[],[],[362,52,12,-3,-3]]); 2. MPSetEqnAttrs('eq1553','',3,[[39,10,0,-1,-1],[53,13,0,-1,-1],[67,16,0,-1,-1],[],[],[],[164,41,1,-3,-3]]) MPEquation() ;

MPSetEqnAttrs('eq1553','',3,[[39,10,0,-1,-1],[53,13,0,-1,-1],[67,16,0,-1,-1],[],[],[],[164,41,1,-3,-3]]); 3. MPSetEqnAttrs('eq1554','',3,[[101,13,3,-1,-1],[135,16,4,-1,-1],[168,20,5,-1,-1],[],[],[],[420,52,12,-3,-3]]) MPEquation() ;

MPSetEqnAttrs('eq1554','',3,[[101,13,3,-1,-1],[135,16,4,-1,-1],[168,20,5,-1,-1],[],[],[],[420,52,12,-3,-3]]); 4. MPSetEqnAttrs('eq1555','',3,[[81,13,3,-1,-1],[109,16,4,-1,-1],[135,20,5,-1,-1],[],[],[],[339,52,12,-3,-3]]) MPEquation() ;

MPSetEqnAttrs('eq1555','',3,[[81,13,3,-1,-1],[109,16,4,-1,-1],[135,20,5,-1,-1],[],[],[],[339,52,12,-3,-3]]); 5. MPSetEqnAttrs('eq1556','',3,[[62,13,3,-1,-1],[81,17,4,-1,-1],[103,21,5,-1,-1],[],[],[],[257,54,13,-3,-3]]) MPEquation()