Планарные графы
Ошибка.
Попробуйте повторить позже
Внутри квадрата отметили 
точек так, что никакие три из 
точек (отмеченных и вершин квадрата) не лежат на одной прямой. Затем
некоторые точки соединили отрезками так, что квадрат разбился на треугольники. Какое количество треугольников при этом могло
получиться?
Подсказка 1
Для начала представим все отмеченные точки и вершины квадрата, как вершины графа, а отрезки и стороны квадрата будем считать ребрами. Тогда у нас есть планарный граф. Попробуйте вывести какое-нибудь соотношение на грани и ребра, учитывая что у нас все грани, кроме внешней являются треугольниками, а внешняя грань содержит только 4 ребра.
Подсказка 2
Выходит, что каждое ребро участвует в двух гранях, а, значит, верно: 3(F - 1) + 4 = 2E. Количество вершин в этом графе нам известно из условия, поэтому попробуйте воспользоваться формулой Эйлера, и найти F.
Будем считать отмеченные точки и вершины квадрата вершинами, а соединяющие их отрезки и стороны квадрата — рёбрами планарного
графа. Для каждого куска, на которые этот граф разбивает плоскость, подсчитаем число ограничивающих его рёбер, и все полученные
числа сложим. Поскольку каждое ребро разделяет два куска, то в итоге получим удвоенное число рёбер. Так как все куски, кроме внешнего
— треугольники, а внешний кусок ограничен четырьмя рёбрами, то верно: 
Заметим, что 
Поэтому по формуле
Эйлера получаем, что:
Решаем это уравнение и получаем 
Так как есть еще внешняя грань, то треугольников 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
