0 / 0 / 0
Регистрация: 12.09.2014
Сообщений: 15
|
|
1 | |
Показать, что в графе знакомств найдется хотя бы один подграф вида треугольника09.12.2015, 16:11. Показов 1257. Ответов 1
Метки нет (Все метки)
Помогите, пжлста решить две задачки по теории графов
1. Имеется n лиц, каждые двое имеют точно одного знакомого. Показать, что в графе знакомств найдется хотя бы один подграф вида треугольника 2. Имеется n лиц, каждые двое имеют точно одного знакомого. Показать, что в графе знакомств не найдется ни одного подграфа вида прямоугольника как вообще можно их описать и доказать, заранее буду благодарна
0
|
09.12.2015, 16:11 | |
Ответы с готовыми решениями:
1
Составьте программу, обнуляющую главную диагональ матрицы, если в ней найдется хотя бы один отрицательный элемент Функции (Составьте программу, обнуляющую главную диагональ квадратной матрицы, если в ней найдется хотя бы один отрицательный элемент) Проверить, что среди первых n^2-1 чисел Фибоначчи найдется хотя бы одно, которое делится на n Найти длину цикла в полном графе с n вершинами, цикл содержит хотя бы один раз каждое ребро |
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
09.12.2015, 16:54 | 2 |
имеется в виду - общего знакомого ?
Если так, тогда решаем. 1. Тут надо еще предположить, что вершин > 1. Возьмем любых двоих А и Б. У них есть знакомый В. Но у В и А тоже есть общий знакомый - Г. АВГ образуют треугольник 2. Предположим противное. Пусть есть 4-х угольник АБВГ. А и В имеют 2-х общих знакомых Б и Г. Противоречие
0
|
09.12.2015, 16:54 | |
09.12.2015, 16:54 | |
Помогаю со студенческими работами здесь
2
Найти в тексте все слова, которые содержат хотя бы один фрагмент заданного вида Найти в тексте все слова, которые содержат хотя бы один фрагмент заданного вида Доказать, что для всякого a є G найдется b є G такое, что a=b^2 Найти вероятность, что хотя бы один не потребует ремонта Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |