Форум программистов, компьютерный форум, киберфорум
Дискретная математика
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 12.09.2014
Сообщений: 15
1

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

09.12.2015, 16:11. Показов 1257. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите, пжлста решить две задачки по теории графов

1. Имеется n лиц, каждые двое имеют точно одного знакомого. Показать, что в графе знакомств найдется хотя бы один подграф вида треугольника

2. Имеется n лиц, каждые двое имеют точно одного знакомого. Показать, что в графе знакомств не найдется ни одного подграфа вида прямоугольника

как вообще можно их описать и доказать, заранее буду благодарна
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.12.2015, 16:11
Ответы с готовыми решениями:

Составьте программу, обнуляющую главную диагональ матрицы, если в ней найдется хотя бы один отрицательный элемент
Дан двумерный массив А(M, M) в виде квадратной матрицы. Составьте про-грамму, обнуляющую главную...

Функции (Составьте программу, обнуляющую главную диагональ квадратной матрицы, если в ней найдется хотя бы один отрицательный элемент)
Дан двумерный массив А(M, M) в виде квадратной матрицы. Составьте программу, обнуляющую главную...

Проверить, что среди первых n^2-1 чисел Фибоначчи найдется хотя бы одно, которое делится на n
Написать программу, которая проверяет, что каково бы ни было натуральное число n, среди первых...

Найти длину цикла в полном графе с n вершинами, цикл содержит хотя бы один раз каждое ребро
формулу или объяснить на примере

1
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
09.12.2015, 16:54 2
Цитата Сообщение от kristinus Посмотреть сообщение
каждые двое имеют точно одного знакомого.
имеется в виду - общего знакомого ?
Если так, тогда решаем.
1. Тут надо еще предположить, что вершин > 1. Возьмем любых двоих А и Б. У них есть знакомый В. Но у В и А тоже есть общий знакомый - Г. АВГ образуют треугольник
2. Предположим противное. Пусть есть 4-х угольник АБВГ. А и В имеют 2-х общих знакомых Б и Г. Противоречие
0
09.12.2015, 16:54
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.12.2015, 16:54
Помогаю со студенческими работами здесь

Найти в тексте все слова, которые содержат хотя бы один фрагмент заданного вида
Исходный текст должен вводиться пользователем с экрана в виде одной или нескольких строк. На экране...

Найти в тексте все слова, которые содержат хотя бы один фрагмент заданного вида
Сама задача: Найти в тексте все слова, которые содержат хотя бы один фрагмент заданного вида....

Доказать, что для всякого a є G найдется b є G такое, что a=b^2
Пусть G — группа нечетного порядка. Доказать, что для всякого a ∈ G найдется b ∈ G такое, что a=b^2

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


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

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