СПРОСИ ПРОФИ
👍
−2
👎 -23

Графы. Дискретная математика.

В древовидном графе есть две вершины степени 4, одна вершина степени 3 и одна вершина степени 2, а остальные вершины являются листьями.

Сколько вершин у этого графа?
Сколько из них листьев?

теория графов дискретная математика высшая математика математика обучение     #1 ⇒   17 фев 2022 16:52   Увидели: 35 клиентов, 558 специалистов   Ответить
👍
0
👎 0

Вам в любом случае нужно знать, что такое «древовидный граф».
Также может помочь знание разных свойств подобных графов, но это не обязательно.

Чтобы разобраться в вопросе с нуля можно провести примерно такое исследование:

1) Нарисуйте любой граф с указанными характеристиками, посчитайте листья.

2) После этого попробуйте придумать ещё один граф, подходящий под условие, но у которого количество листьев будет другим.

3) Когда много раз попробуете и ничего не получится — возможно, появятся идеи, в чём проблема.
Строгое рассуждение, объясняющее феномен, и будет решением задачи.

  ⇐ #2 ⇒   17 фев 2022 17:29   Ответить
👍
0
👎 0

5 вершин, 2 листьев

  ⇐ #3 ⇒   18 фев 2022 23:02   Ответить
👍
0
👎 0

Если 2 листа, то получается 6 всего. К тому же по количеству рёбер не сходится.
Сумма степеней должна быть в два раза больше количества рёбер. Составляем уравнение.
2 * (n — 1) = 4 * 2 + 3 + 2 + (n — 4)
2 * n — 2 = 9 + n
n = 11
Ответ: 11 вершин, из них 7 листьев.

  ⇐ #4   19 фев 2022 01:47   Ответить

Задайте свой вопрос по высшей математике
профессионалам

● Сейчас онлайн 75 репетиторов по высшей математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 0

Комбинаторика_свойство чисел Стирлинга 1-го рода_коэффициенты многочлена   0 ответов

Добрый день!

Можно ли обратиться к Вам по следующему вопросу? Как известно числа Стирлинга первого рода являются коэффициентами при обычных степенях при разложении факториальной степени на сумму обычных степеней. И это свойство чисел Стирлинга связано с циклической структурой подстановки. Можно для начала спросить у Вас, есть ли где-нибудь именно комбинаторное доказательство (а еще лучше объяснение, как например, комбинаторно объясняют биноминальные…
  17 фев 2018 19:00  
👍
+2
👎 2

Задача про граф   3 ответа

В графе 100 черных вершин, 50 белых и есть еще зеленые. Каждая зеленая вершина смежна ровно с одной черно-белой парой, то есть ровно с одной черной вершиной и ровно с одной белой. Никакие три зеленые вершины не смежны с одной и той же черно-белой парой. Какое наибольшее количество зеленых вершин может быть в этом графе?

Я вроде придумала максимизирующую конструкцию, но не получается доказать ее максимальность...
  28 фев 2017 14:56  
ASK.PROFI.RU © 2020-2025