ТолВИКИ - Вклад участника [ru]

Семинар ДООМ "Решение задач на применение теории графов"

2007-12-03T17:59:10Z

Denis: Новая: '''УРОК №2.''' Тема: Решение задач на применение теории графов. Цели: - повт...

'''УРОК №2.'''

Тема: Решение задач на применение теории графов.

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

АКТУАЛИЗАЦИЯ:

1).Что называется графом; приведите примеры, где в практической деятельности встречаются графы?
2).Кому принадлежит первая работа по теории графов?
3).Какие графы называются полными и неполными?
4).Как подсчитать количество ребер графа, имеющего n-вершин?
5).Что называется степенью графа?
6).Какая вершина называется четной и нечетной?
7).Какой граф называется однородным?
8).Чему равна сумма степеней всех вершин графа?

Задача 1 (устно). Докажите, что не существует графа с пятью вершинами, степени которых 4, 4, 4,2?

Задача 2. (устно). В одном городе всего 25 телефонов. Можно ли их соединить проводами так,
чтобы каждый телефон был соединен ровно с пятью другими?

ОТРАБОТКА НАВЫКОВ РЕШЕНИЯ ЗАДАЧ.

ЗАДАЧА 1. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга в этом классе,
11 – по 4 друга, а 10 – по 5 друзей?

РЕШЕНИЕ: представим граф с тридцатью вершинами, у которого 9 вершин имеют степень 3, 11 – степень 4, 10 – степень 5, следовательно, у этого графа 19 нечетных вершин, что противоречит закономерности: число нечетных вершин графа четно. Значит, не может.

ЗАДАЧА 2. В трех различных домах живут три поссорившихся соседа. Недалеко от их домов
расположены три колодца. Можно ли от каждого дома провести к каждому из колодцев тропинку так,
чтобы никакие 2 из них не пересекались?

Решение: Построим граф , где дома обозначим буквами А, В, С, а колодцы цифрами 1, 2, 3.

[[Изображение:Urok_2_1.JPG]]

По рисунку видно, что нельзя.

ЗАДАЧА 3. В государстве система авиалиний устроена так, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно проехать, сделав не более одной пересадки. Какое максимальное число городов может быть в этом государстве?
РЕШЕНИЕ: построим граф , по которому показаны существующие авиалинии.

[[Изображение:Urok_2_2.JPG]]

Если существует некоторый город N, то из него можно добраться не более, чем до трех городов, а из каждого из них не более чем до двух. Тогда всего городов не более чем 1+3+6=10.

САМОСТОЯТЕЛЬНАЯ РАБОТА ( по вариантам).

1 вариант.

ЗАДАЧА. В государстве 100 городов и из каждого из них выходит 4 дороги. Сколько всего дорог в
государстве?

ЗАДАЧА. Можно ли фигуру, изображенную на рисунке, начертить одним росчерком пера? Ответ обоснуйте.

[[Изображение:Urok_2_3.JPG]]

2 вариант.

ЗАДАЧА. В государстве52 города и из каждого выходит 4 дороги. Сколько всего дорог в
государстве?

ЗАДАЧА. Можно ли фигуру, изображенную на рисунке, начертить одним росчерком пера?

[[Изображение:Urok_2_4.JPG]]

Файл:Urok 2 4.JPG

2007-12-03T17:30:12Z

Denis: Урок 2 рисунок 4

Урок 2 рисунок 4

Файл:Urok 2 3.JPG

2007-12-03T17:28:51Z

Denis: Урок 2 рисунок 3

Урок 2 рисунок 3

Файл:Urok 2 2.JPG

2007-12-03T17:27:43Z

Denis: Урок 2 рикунок 2

Урок 2 рикунок 2

Файл:Urok 2 1.JPG

2007-12-03T17:25:55Z

Denis: Урок 2 рисунок 1

Урок 2 рисунок 1

Дистанционный методический семинар ДООМ

2007-12-03T17:11:02Z

Denis: /* Участники семинара */

'''Уважаемые педагоги, локальные координаторы команд-участниц ДООМ'''! Отдельные заявки на участие в семинаре «Теория графов в школьном курсе математики и информатики» присылать не нужно.

== Как стать Участником семинара ==

'''I. Руководители команд (локальные координаторы) должны зарегистрироваться в ТолВики под своим реальным именем (для не зарегистрировавшихся ранее). Для этого нужно:

* В верхнем правом углу любой страницы нажать ссылку '''Представиться системе'''.
* На вопрос "Вы ещё не зарегистрировались?" кликнуть '''Создать учётную запись'''.
* В появившихся формах введите Имя участника – то имя, под которым вы будете отображаться на сайте (желательно в формате - Фамилия Имя Отчество), пароль - сочетание знаков, которое необходимо для каждого последующего входа в систему.
* Заполните также поле '''Ваше настоящее имя'''. Это будет способствовать комфортному общению и сделает более удобной работу участников.

<center>[[Изображение:Reg_lk_doom.jpg]] <br>
Рис. 1.
</center>

* Затем нажмите '''Зарегистрировать нового участника'''.
* Заполните (не обязательно) '''Личную страницу участника''' методического семинара (см. пример [[Участник:Васильева Александра|Васильева Александра]]).

'''II. Создать статью Семинар ДООМ YYY (где YYY название (тема) статьи). Для этого:

* Введите в окно '''Поиск''' в левой части экрана на странице ТолВики '''имя статьи''', которую Вы хотите написать, и нажмите кнопку '''Перейти'''. Внимание! Название статьи обязательно должно начинаться со слов «'''Семинар ДООМ'''». Если такая статья уже есть, то система предложит Вам ее для чтения и правки (если это не Ваша статья, измените название статьи, создаваемой Вами, и повторите действия, начиная с п. II.).
* Если такой статьи еще нет, то появится ссылка '''Создать страницу''', окрашенная в красный цвет.
* Нажав ссылку, Вы окажетесь в окне редактирования будущей статьи. В верхней части окна редактирования будет надпись с названием вашей статьи: '''Редактирование:Название статьи'''. Внимание! Ваша статья уже названа, и поэтому не нужно еще раз писать название внутри статьи.
* В окне редактирования поместите Вашу статью. Внимание! В начале статьи под ее названием '''обязательно укажите автора и Идентификационный номер команды'''. (Если '''Личная страница участника''', полученная при регистрации, была Вами заполнена, сделайте на нее ссылку с имени автора (например, <nowiki>[[Участник:Васильева Александра]]</nowiki>), а с '''Личной страницы участника''' ссылку на статью (т.е. на Личной странице, поместить запись <nowiki>[[Семинар ДООМ YYY]]</nowiki>, где YYY – название (тема) статьи)).
* Нажмите кнопку '''Предварительный просмотр'''. Экран будет разделен на два окна. В одном окне отображается текст в том виде, как он будет выглядеть на сайте, а второе окно – это окно редактирования. Вносите изменения во втором окне, нажимая периодически кнопку Предварительный просмотр, в первом - отслеживайте внесённые правки.
* '''Обязательно''' в конце статьи следует указать в двойных квадратных скобках (через двоеточие, без пробелов) одну или несколько категорий, в которых разместится Ваша статья. Например, '''[[Категория:Проект ДООМ]]'''.
* Статья будет считаться незаконченной, если в ней отсутствуют внутренние и внешние ссылки.
* Нажмите кнопку '''Записать страницу'''.
* Для перехода в режим правки нажмите вверху вкладку «'''Править'''».

'''III. Разместите на сайте проекта ДООМ в разделе «Дистанционный методический семинар» внутреннюю ссылку на свою статью в следующем формате: ФИО автора, (Идентификационный номер команды), название статьи (если Вы являетесь автором нескольких статей, просто перечислите их). Для этого нужно:

* Нажать на ссылку [править] в разделе "Участники семинара".

<center>[[Изображение:Prav_sem_doom.jpg]]<br>
Рис. 2.</center>

* Записать ФИО автора, затем название статьи в двойных квадратных скобках (например, Васильева Александра Сергеевна, 777, <nowiki>[[Семинар ДООМ YYY]]</nowiki>).
* Нажать Записать страницу.
* Если название статьи будет красного цвета, значит, Вы сделали что-то неправильно. Проверьте себя, внесите исправления и повторите попытку.

'''Внимание!'''
Свои отзывы, комментарии и реплики на статьи других участников семинара нужно оставлять на странице обсуждаемой статьи во вкладке '''«Обсуждение».''' Для этого:
* Откройте статью, заинтересовавшую вас (на сайте проекта ДООМ в разделе «Дистанционный методический семинар»), затем вкладку '''«Обсуждение», «Править»''' и впишите нужный текст.
* Нажмите кнопку '''«Ваша подпись и момент времени»''' на панели визуального редактора, чтобы подписать свою работу.
* Нажмите кнопку '''Записать страницу'''.

'''Не забывайте''' представляться при работе в ТолВики. Для этого нужно выполнять следующие действия:
* В правом верхнем углу экрана выбрать ссылку [[Служебная:Userlogin|Представиться системе]].
* В окнах "Ваше имя участника" и "Ваш пароль" ввести логин и пароль, выбранные при регистрации.
* Щелкнуть по кнопке "Представиться системе".

== Участники семинара ==

# [[Участник:Пенкина Любовь Ивановна|Пенкина Любовь Ивановна]],005,[[Семинар ДООМ. Знакомство с графами (5 класс)]]
# [[Участник:Иванова Елена|Иванова Елена Андреевна]], 025,[[Семинар ДООМ "Электронный обучающий ресурс"]]
# [[Участник:Москевич Лариса Вячеславовна|Москевич Лариса Вячеславовна]], 061,[[Семинар ДООМ: Первая встреча с графом.]],[[Семинар ДООМ Решение вероятностных задач с помощью построения «древа» исходов.]]
# [[Участник:Октысюк Ульяна Святославовна|Октысюк Ульяна Святославовна]], 069, [[Семинар ДООМ урок математики "Графы"]]
# [[Участник:Янина Ирина Владимировна|Янина Ирина Владимировна]], 053, [[Семинар ДООМ. Решение комбинаторных задач с помощью графов]], [[Семинар ДООМ. Сетевой график]]
# [[Участник:Круглова Валентина Николаевна|Круглова Валентина Николаевна]], 006, [[Семинар ДООМ "Игра ЧТО? ГДЕ? КОГДА?"]]
# [[Участник:Хазова Людмила Модестовна|Хазова Людмила Модестовна]], [[Участник:Многогранник 041|041]], [[Семинар ДООМ. Использование графов при решении задач]], [[Семинар ДООМ. Решение комбинаторных задач]], [[Семинар ДООМ. Графы при решении задач]]
# [[Участник:Лесных Марина Владимировна|Лесных Марина Владимировна]], [[Участник:Следопыт 071|071]],[[Участник:Метеор 027|027]], [[Семинар ДООМ. Впечатление о проекте]]
# [[Участник:Коннова Елена|Коннова Елена Генриевна]],[[Участник:Альтаир 062|062]], [[Участник:Форсаж 063|063]], [[Семинар ДООМ Некоторые уточнения для лучшего взаимопонимания]], [[Семинар ДООМ Элективный курс Графы]], [[Семинар ДООМ Материалы для курса Графы]]
# [[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]],022,[[Семинар ДООМ "Основы графики Паскаля"]]
# [[Участник:Невзорова Марина Евгеньевна|Невзорова Марина Евгеньевна]],002,[[Семинар ДООМ Уникурсальные кривые (фигуры)]]
# [[Участник:Болонина Людмила Александровна|Болонина Людмила Александровна]],022,[[Семинар ДООМ "Из опыта изучения элементов теории графов."]],022,[[Семинар ДООМ "Применение графов к решению логических задач."]]
# [[Участник:Трифонова Валентина Артемьевна|Трифонова Валентина Артемьевна]],022,[[Семинар ДООМ "Основные понятия теории графов."]],022,[[Семинар ДООМ "Решение задач на применение теории графов"]]
# [[Участник:Шувалова Юлия Григорьевна|Шувалова Юлия Григорьевна]],[[Участник:Львы_40|040]],[[Семинар ДООМ "Можно ли не ломая проволоки изготовить каркас куба?"]]

[[Категория:Проект ДООМ]]