Статистика
Всего в нашей базе более 4 327 664 вопросов и 6 445 983 ответов!

Докажите, что если граф не содержит циклов и имеет n вершин и n-1 ребро, то он связен.

5-9 класс

Sevana23 28 мая 2013 г., 10:38:25 (11 лет назад)
Рейтинг
+ 0 -
0 Жалоба
+ 0 -
Vipshapirko
28 мая 2013 г., 13:06:42 (11 лет назад)

Предположим, что это не так, тогда какие то две вершины не соединены. Будем так же отбрасывать "одиночные" вершины. Тогда по нашему предположению должно остаться 2 или больше не связанных вершины в конечном графе, где нет ребер. Чего быть не может, т.к. иначе кол-во ребер и вершин отличались на 2 или более, а не на 1.

Ответить

Другие вопросы из категории

Помогите решить! Кто сколько может!

1) Разложите на множители
16x^{2}c-9c
2) Представьте в виде одночлена стандартного вида
10 p^{4} c^{4} (0.1pc)^{3}
3) Упростите выражение
(2x+1)(2x-1)+(2x-1)^{2}

4) Это задание прошу сделать на листочке ну или написать чтобы понятно было
Решите графически систему уравнений

 \left \{ {{x-2y=6} \atop {3x+2y=-6}} \right.

0.97x+3.78x-15.215=43.21
ПОМАГИТЕ СРОЧНО!!!

НА прямолинейном участке железнодорожного пути уложены рельсы,длинна каждого из которых 12,5 м.Сколько рельсов уложено на 300 метров пути.решение

3000 грамм сколько килограмм

Читайте также

Докажите, что значение данного выражения не зависит от значения х:

(5х-7)+10(х-2)+3(12-5х)=
7(3х-4)-4(4х+3)-5(х-1)=
Докажите, что значение данного выражения не зависит от значений х и у:
1. 3(3х-у+2)-6(2х-у-3+5)+3(х-у+5)=
2. 25(2х-4у-1)-6(5х-11у+7)-2(10х-17у+3)=

1. докажите, что выражение (y-5)(y+10)-5 (y-11) при любом значении y принимает положительное значение.

2. докажите, что при любом целом y значение выражения 40y+(y-8)^2 -y(y-16) кратно 8.

3.при каком значении c многочлен стандартного вида, тождественно равный произведению (s^2+5s-7)(s-c),не содержит s^2?

Помогите хотябы какой нибудь сделать. 1. Коридор длины l покрыт конечным числом дорожек. Докажите, что можно убрать часть из них так, чтобы

оставшиеся дорожки по-прежнему покрывали коридор и суммарная их длина не превышала бы 2l .
2. Клетки таблицы n x n заполнены числами 1.2...n так, что каждое число встречается ровно n раз. Докажите, что в некоторой строчке или в некотором столбце встречается не менее корень n различных чисел.
3. Камни, сложенные в n куч, собрали и разложили в n+k куч. Докажите, что не менее k+1 камня оказались в кучках меньших, чем те, в которых они лежали.
4. В 100-элементном множестве выбрано 101 трёхэлементное подмножество. Докажите, что найдутся два подмножества, пересекающиеся ровно по одному элементу.
5. Рёбра графа покрашены в d больше1 цветов так, что в любом пути из трёх различных рёбер (возможно, замкнутом) первое и последнее ребро окрашены в разные цвета. Докажите, что вершины графа можно правильным образом раскрасить в цветов
6. Дана бесконечная в обе стороны клетчатая полоска. Двое играют в “крестики-нолики”. Первый каждым ходом ставит три крестика, а второй два нолика. Сможет ли первый игрок поставить 100 крестиков подряд?



Вы находитесь на странице вопроса "Докажите, что если граф не содержит циклов и имеет n вершин и n-1 ребро, то он связен.", категории "математика". Данный вопрос относится к разделу "5-9" классов. Здесь вы сможете получить ответ, а также обсудить вопрос с посетителями сайта. Автоматический умный поиск поможет найти похожие вопросы в категории "математика". Если ваш вопрос отличается или ответы не подходят, вы можете задать новый вопрос, воспользовавшись кнопкой в верхней части сайта.