Какое наибольшее число городов может быть в этом государстве? 6. Докажите, что в любом связном графе можно удалить вершину со всеми выходящими из нее ребрами. так, чтобы он остался связным.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
ЮНИ
-
центр
-
XXI


8 класс

Графы


Двудольные графы

1.

В восьмом классе некоторой школы каждый мальчик дружит с 5
-
ю девочками и 6
-
ю
мальчиками, а каждая
девочка дружит с 6
-
ю мальчиками и 5
-
ю девочками. А)

Сколько школьников учится в этом классе, если
известно, что их не более тридцати? Б) А если их не более

35?

2.

Перед началом уроков классный руководитель заметил, что каждый учащийся его

класса поздоровался за руку с
шестью девочками и восемью мальчиками. При этом количество рукопожатий между мальчиками и девочками
было на пять меньше числа остальных рукопожатий. Сколько учеников в классе?

3.

На олимпиаду по математике прибыло несколько учащ
ихся 8 класса. Некоторые из них оказались уже
знакомыми. При встрече Маша улыбнулась своему знакомому Саше, а Коля улыбнулся незнакомой ему девочке
Оле. И вообще, каждая восьмиклассница улыбнулась каждому знакомому ей восьмикласснику, а каждый
восьмиклассн
ик улыбнулся незнакомой ему восьмикласснице. В результате было зафиксировано 155 улыбок.
Сколько всего учащихся 8 класса участвовало в олимпиаде?

4.

В некотором классе некоторой школы 15 учениц. Каждая из них послала каким
-
то 7 своим одноклассницам
перед Нов
ым Годом по открытке. Оказалось, что староста класса Галя получила ровно 6 открыток. А) Докажите,
что среди этих 15 одноклассниц найдутся две, которые обменялись открытками (т.е. послали открытки друг
другу). Б) Может ли таких, обменявшихся открытками одно
классниц, быть только две? В) А ровно 4, т.е. две
пары?


Разное

5.

В некотором государстве система авиалиний устроена так, что любой город соединен авиалинией не более чем с
тремя другими городами, и из любого города в любой другой можно попасть, сделав не
более одной пересадки.
Какое наибольшее число городов может быть в этом государстве?

6.

Докажите, что в любом связном графе можно удалить вершину со всеми выходящими из нее ребрами
так, чтобы он остался связным.

7.

Докажите, что в любом связном графе две длинней
шие простые цепи имеют общую вершину.

8.

Докажите, что граф двудолен тогда и только тогда, когда всякий цикл в нем имеет четную длину.











ЮНИ
-
центр
-
XXI


8 класс

Графы


Двудольные графы

1.

В восьмом классе некоторой школы каждый мальчик дружит с 5
-
ю девочками и 6
-
ю мальчиками, а каждая
девочка дружит с 6
-
ю мальчиками и 5
-
ю девочками. А)

Сколько школьников уч
ится в этом классе, если
известно, что их не более тридцати? Б) А если их не более

35?

2.

Перед началом уроков классный руководитель заметил, что каждый учащийся его класса поздоровался за руку с
шестью девочками и восемью мальчиками. При этом количество руко
пожатий между мальчиками и девочками
было на пять меньше числа остальных рукопожатий. Сколько учеников в классе?

3.

На олимпиаду по математике прибыло несколько учащихся 8 класса. Некоторые из них оказались уже
знакомыми. При встрече Маша улыбнулась своему зн
акомому Саше, а Коля улыбнулся незнакомой ему девочке
Оле. И вообще, каждая восьмиклассница улыбнулась каждому знакомому ей восьмикласснику, а каждый
восьмиклассник улыбнулся незнакомой ему восьмикласснице. В результате было зафиксировано 155 улыбок.
Сколь
ко всего учащихся 8 класса участвовало в олимпиаде?

4.

В некотором классе некоторой школы 15 учениц. Каждая из них послала каким
-
то 7 своим одноклассницам
перед Новым Годом по открытке. Оказалось, что староста класса Галя получила ровно 6 открыток. А) Докажи
те,
что среди этих 15 одноклассниц найдутся две, которые обменялись открытками (т.е. послали открытки друг
другу). Б) Может ли таких, обменявшихся открытками одноклассниц, быть только две? В) А ровно 4, т.е. две
пары?


Разное

5.

В некотором государстве
система авиалиний устроена так, что любой город соединен авиалинией не более чем с
тремя другими городами, и из любого города в любой другой можно попасть, сделав не более одной пересадки.
Какое наибольшее число городов может быть в этом государстве?

6.

Докаж
ите, что в любом связном графе можно удалить вершину со всеми выходящими из нее ребрами
так, чтобы он остался связным.

7.

Докажите, что в любом связном графе две длиннейшие простые цепи имеют общую вершину.

8.

Докажите, что граф двудолен тогда и только тогда, ко
гда всякий цикл в нем имеет четную длину.


Приложенные файлы

  • pdf 41309935
    Размер файла: 188 kB Загрузок: 0

Добавить комментарий