В плоском двусвязном графе 7 граней (считая внешнюю) – 3 треугольника, 3 четырёх- угольника и пятиугольник. Сколько в этом графе вершин и рёбер? Приведите пример диаграммы графа.

задан 3 Фев '19 1:28

Сумма периметров граней равна 26, поэтому рёбер 13 (каждое ребро лежит на границе двух граней, считая внешнюю). По формуле Эйлера для сферических графов, В-Р+Г=2 (это с учётом внешней грани), откуда В=8.

Зная числа, легко рисуем пример такого графа. Скажем, сначала склеиваем три 4-угольника, получая 8-угольник. Потом добавляем с внешней стороны треугольники в количестве 3 штук. На границе возникает 5-угольник.

(3 Фев '19 4:07) falcao

@falcao: спасибо большое

(3 Фев '19 11:12) Flexibility

@falcao: Я подумал над вашими размышлениями, сразу говорю, что могу быть не прав, однако меня смущает появление восьмиугольника. Как я понял задание состоит в том, чтобы при построении мы имели только 3 треуг-ка, 3 - четырехуг-ка, 1 пятиугольник. Попробую проиллюстрировать, что я имею в виду. Не могу сюда прикрепить, отправлю фото на почту. Это самое близкое, что мне удалось построить.

(3 Фев '19 12:43) Flexibility

@EXODUS: я видел Ваш рисунок, присланный по почте. Он совершенно не соответствует действительности. Надо иметь в виду, что грани -- это связные компоненты плоскости, из которой удалены рёбра графа. Это как если бы мы ножницами всё прорезали. Никакого 8-угольника при этом не возникает, так как он разрезается, и всё распадается на фигуры, заданные в условии. Одна из них будет внешней частью пятиугольника.

То есть гранями считаются только те области, внутри которых пусто. Это отличается от головоломок типа "сколько прямоугольников вы видите на рисунке?", когда учитывается всё.

(3 Фев '19 14:42) falcao

@falcao: понял, это я и хотел уточнить. Спасибо

(3 Фев '19 15:30) Flexibility
10|600 символов нужно символов осталось
0

@falcao Могу узнать как вы добавляете три внешних треугольника без дополнительных вершин?

ссылка

отвечен 13 Июл '19 2:47

@Жирайр: здесь все треугольники криволинейные. Если есть 8-угольник ABCDEFGH, то я провожу во внешней его части дугу AC, что означает добавление к рисунку треугольника ABC. Новых вершин при этом не возникает. Аналогично добавляем дуги CE, EG. Получается криволинейный 5-угольник ACEGH.

(13 Июл '19 2:54) falcao

я вас понял, спасибо! Но, наверное, можно было ограничиться прямолинейными фигурами. https://pp.userapi.com/c852136/v852136413/1621c8/R1kF0Ibkozs.jpg

(13 Июл '19 13:19) classman
1

@Жирайр: да, можно -- есть известная теорема о том, что всякий простой плоский граф может быть уложен на плоскости так, что все его рёбра будут отрезками.

Здесь я всё описывал словесно, поэтому выбрал первый попавшийся достаточный для достижения цели способ.

(13 Июл '19 17:45) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,561
×581

задан
3 Фев '19 1:28

показан
1034 раза

обновлен
13 Июл '19 17:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru