Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Театральный программный пульт управления световым оборудованием Compulite Vector System Large LX-Red (8192 DMX канала – 4096 на внутренних DMX выходах...полностью>>
'Документ'
07.1981 Минкульт НКО Мальсагова Зарема Абукаровна 1 .03.199 Институт экономики и правоведения Дадиани Теона Владимировна 18....полностью>>
'Документ'
честность, коммуникабельность, пунктуальность, трудолюбие, ответственность, нацеленность на результат, активная жизненная позиция, аналитический склад...полностью>>
'Документ'
После отступа в один интервал следует название статьи. Название работы следует печатать заглавными буквами, жирным шрифтом, выравнивание по центру. По...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Опять увидеть граф: счет вершин, ребер и компонент связности

14 ноября 2013, гр. 9-1

Считаем ребра, вершины и компоненты без циклов

Обозначим в графе В – число вершин, Р – число ребер, С – число компонент связности.

Факт 1. а) В дереве (то есть связном графе без циклов) В=Р+1.
б)
В графе без циклов В=Р+С

Факт 2. а) В связном графе РB–1. б) В любом графе РВ–С.

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

2+. По кругу расположены монеты, чередуясь: три подряд орлом вверх, три подряд – решкой, три – орлом, три – решкой и т. д – всего 10 групп по 3 монеты. Если у монеты двое соседей лежат по-разному, ее можно перевернуть. Какое наибольшее число монет можно положить орлом вверх с помощью таких операций?

3+. Какое наибольшее число клеток доски 99 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?

Считаем ребра в двудольном графе

Факт 3. Сумма степеней белых (черных) вершин равна числу ребер двудольного графа.

Факт 4. а) В двудольном графе с 2n вершинами не более n2 ребер.
б) В двудольном графе с 2n+1 вершинами не более n(n+1) ребер.

4. Футбольный мяч сшит из 32 лоскутков – шести- и пятиугольников. Пятиугольники между собой не граничат, каждый пятиугольник граничит с пятью шестиугольниками, а каждый шестиугольник – с тремя пятиугольниками и тремя шестиугольниками. Сколько лоскутков пятиугольны?

5. а) В ряд выписаны 14 целых чисел. Рассматриваются всевозможные попарные разности. Какое наибольшее количество из этих разностей может быть нечётными?

б) В ряд выписаны 20 целых чисел. Каково наибольшее число нечетных последовательных сумм?

6+. Даны 10 чисел a1, a2, …, a10. Известно, что среди попарных сумм ai+aj (i  j) как минимум 37 целых. Докажите, что все числа 2a1, 2a2, …, 2a10 – целые.

Опять увидеть граф: на дом

ОУГ1. На свободные поля шахматной доски по одному выставляются короли. Первый выставляется произвольно, каждый следующий должен бить нечетное число ранее выставленных. Какое наибольшее число королей можно выставить?

ОУГ2. В Зурбагане сеть железных дорог устроена так: все города стоят на кольце; кроме того, столица соединена отдельными ветками с каждым из городов, кроме соседей по кольцу. Правительство Зурбагана разбило сеть на участки между соседними городами и постановило разделить эти участки между двумя компаниями так, чтобы можно было проехать между любыми двумя городами как по дорогам только первой компании, так и по дорогам только второй компании. Можно ли выполнить постановление правительства?

ОУГ3. В классе 30 человек. За месяц было 29 дежурств, в каждом дежурила пара учеников. Докажите, что можно так выставить всем ученикам класса по одной оценке по 5-балльной шкале, что будет выставлена хотя бы одна пятерка, и в каждой паре дежуривших сумма оценок будет равна 8. (Сдать письменно)

ОУГ4. Хозяйка испекла для гостей пирог. За столом может оказаться либо p человек, либо q (p и q взаимно просты). На какое минимальное количество кусков (не обязательно равных) нужно заранее разрезать пирог, чтобы в любом случае его можно было раздать поровну?

Московские сборы, 9 класс, А.Шаповалов,



Похожие документы:

  1. Опять увидеть граф: счет вершин и ребер

    Документ
    ... Опять увидеть граф: счет вершин и ребер 13 ноября, гр. 9-2 Разбиение на циклы и цепочки Факт 1. Если в конечном графе ... ребра, вершины и компоненты связности Обозначим в графе В – число вершин, Р – число рёбер, С – число компонент связности. Факт ...
  2. Образовательный стандарт образовательная система «Школа 2100»

    Образовательный стандарт
    ... Накапливать опыт ... умения увидеть художественное ... компонент Логико-алгоритмический компонент ... 49 Счет сотнями. ... графов («Строим графы») 1 Урок-путешествие Граф. Вершины и ребра графа ... графах, выделять части (часть) ребер графа ... (связность, цельность ...
  3. Учебник для студентов высших учебных заведений

    Учебник
    ... как граф, со- стоящий из вершин и ... научения впервые был получен Ребером в 1967 г. ( ... с точки зрения связности се компонентов, множества симуль- ... именно это обстоятельство позволило увидеть природу человечес- кого ... за счет опоры на внутренний опыт и ...
  4. Д. К. Самин 100 великих архитекторов

    Документ
    ... своеобразную вершину развития ... счет не поставить, а как он служить больше не хощет, опять ... графа М. Воронцова к графу ... вертикальных ребер ... из трех компонентов: пространства, ... физическую связность огромной ... поколения, стремился увидеть мир непосредственно ...
  5. Контрольные вопросы 23

    Контрольные вопросы
    ... и, в конечном счете, к становлению ... выделить множество вершин и ребер. Каждая вершина графа представляет ... вообще не увидят каких-либо ... • опыт работы с системным ПО; • опыт работы ... Анализ связности (прочности и сцепления) компонентов предметной области ...

Другие похожие документы..