37 / 26 / 1
Регистрация: 31.03.2019
Сообщений: 585
1

Найдите количество различных неориентированных связанных графов на четырех различных вершинах

31.01.2020, 04:52. Показов 2833. Ответов 5

Author24 — интернет-сервис помощи студентам
Найдите количество различных неориентированных связанных графов на четырех различных вершинах. Например, для трех вершин таких графов четыре.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.01.2020, 04:52
Ответы с готовыми решениями:

Найдите количество всех различных наборов из четырех четных чисел
"Найдите количество всех различных наборов из четырех четных чисел (int a,b,c,d), для которых будет...

Найдите количество различных программ
Программы исполнителя: 1. умножить число на 5; 2. прибавить к числу 1. Программа для исполнителя...

Найдите количество различных элементов массива
Помогите написать простую программу С клавиатуры вводится массив размером например 5 чисел....

Количество различных упорядоченных пар различных слов
Решил прорешать демо задачи в олимпиаде по программированию в Яндексе, и не могу справиться с одной...

5
37 / 26 / 1
Регистрация: 31.03.2019
Сообщений: 585
01.02.2020, 16:59  [ТС] 2
ответ получился 38
правильный ли ответ?
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
03.02.2020, 16:30 3
Лучший ответ Сообщение было отмечено goldolov_na как решение

Решение

goldolov_na, Имеются в виду неизоморные? Или с отмеченными вершинами?
Неизоморфных много меньше.
С отмеченными вершинами 26 = 64. Из них связных несколько меньше.

Добавлено через 10 минут
С отмеченными у меня получилось 64 - 4*4 - 6 - 1 = 41
ЗЫ. Советую (после уточнения) перенести тему в раздел "Математика - Дискретная математика"
1
Эксперт по математике/физике
4172 / 3042 / 916
Регистрация: 19.11.2012
Сообщений: 6,188
04.02.2020, 13:32 4
Цитата Сообщение от goldolov_na Посмотреть сообщение
таких графов четыре.
Судя по тому, сколько получилось графов на трех вершинах, речь о графах с помеченными вершинами. Связных графов на четырех вершинах с точностью до изоморфизма 6 штук: простая цепь (12), звезда с тремя лучиками (4), треугольник с отростком (12), квадрат (3), квадрат с одной диагональю (6), тетраэдр (1). В скобках указано сколько возможностей занумеровать вершины.
Получилось 38. Проверяйте.
1
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
04.02.2020, 14:13 5
kabenyuk, я считал несвязанные. Считал так
с одной изолированной вершиной 4(вершины)*4(3-графа)
с 2-мя изолированными 6
все изолированы 1
Пропустил! Пара отрезков 6
Итого 29
64(всего) - 29 = 35
Где я ошибся?
....
Понял! Пара отрезков - 3 (6/2)
1
37 / 26 / 1
Регистрация: 31.03.2019
Сообщений: 585
04.02.2020, 16:40  [ТС] 6
Байт, я решил это через код(машинно) и получил такую таблицу:
1 1
2 1
3 4
4 38
5 728
6 26704

Байт, да у вас неправильно
правильный ответ 38

Добавлено через 3 минуты
Байт, либо кодом можно было либо так:
Между четырьмя различными вершинами можно провести 6 ребер, поэтому
общее число графов на четырех вершинах равно 26
= 64. Подсчитаем число несвязных
графов:
1) три вершины образуют связную компоненту (4-мя способами) + отдельностоящая
вершина; всего таких графов 4 × 4 = 16;
2) две связные компоненты по две вершины – 3 варианта;
3) две вершины соединены, а две другие – нет: 6 вариантов;
4) ребер в графе нет – 1 вариант.
64 – (16 + 3 + 6 + 1) = 38.
Ответ. 38
1
04.02.2020, 16:40
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.02.2020, 16:40
Помогаю со студенческими работами здесь

Способы распределение a различных бананов, b различных яблок и c различных груш
Влад хочет взять с собой для ланча пару фруктов. У него есть a различных бананов, b различных яблок...

Найдите количество различных вариантов раскраски сторон правильного пятиугольника
Найдите количество различных вариантов раскраски сторон правильного пятиугольника в восемь цветов...

Массив: Найдите количество различных по модулю чисел среди элементов массива
Задан отсортированный массив целых чисел. Найдите количество различных по модулю чисел среди...

В массиве найдите количество серий из четверок подряд идущих попарно различных элементов
В массиве найдите количество серий из четверок подряд идущих попарно различных элементов.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru