Теория графов. 2
СОДЕРЖАНИЕ
Введение…………………………………………………………
Глава 1. Графы и их применение………………………………………………..
1.1. Основные понятия теории
1.2. Раскраска графов. Применение
раскраски графов в
Глава 2. Элементы теории графов на факультативных занятиях в школе….22
2.1. Роль факультативных занятий………
2.2. Постановка факультатива «
Заключение……………………………………………………
Список использованной литературы………………………………………..35
ВВЕДЕНИЕ
Что такое граф? Когда речь заходит о графе, большинство людей представляют себе график, т.е. нечто вроде диаграммы, отражающей производственную деятельность какого-нибудь предприятия (рис. 1), или гладкую кривую (рис. 2), позволяющую наглядно представить свойства какой-нибудь математической функции.
Рис. 1 Рис. 2
Но для огромного (и все возрастающего) числа математиков слово «граф» означает нечто совсем иное.
Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах. Однако, эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен, главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это, благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развития формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач – проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять лет и даже двадцать вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем биологии и психологии.
Настоящая работа состоит из двух глав.
В первой главе освещаются методы теории графов. В частности, даются ключевые понятия и определения этой теории, рассматриваются различные способы представления графов, деревьев и раскраски графов, а также особенности применения этих методов в различных сферах.
Вторая глава включает в себя факультативный курс в старшей школе с приложением разработки факультатива.
Раздел теоретического изложения материала подкреплен практическими задачами и упражнениями.
Глава 1. ГРАФЫ И ИХ ПРИМЕНЕНИЕ
1.1 Основные понятия теории графов
Пусть дано множество V = {v1, v2,…,vn} и пусть на множестве V определено семейство U = {u1, u2, …, un} пар элементов Uk = {vi, vj}, (k=1, m) произвольной кратности и упорядочения. Пара {V, U} называется графом. Граф, как правило, обозначают прописными латинскими буквами, например G, H. Принято также писать G (V, U) для того, чтобы определить некоторый конкретный граф G.
Элементы v1, v2,…, vn называют вершинами графа, а пары Uк = {vi, vj},
(к = 1, m) – ребрами.
Определению графа можно дать такую интерпретацию. Пусть имеем описание графа:
G (V, U) = {{v1, v2,…, v6}, {{v1, v3}, <v5, v1>, {v3, v4}, <v2, v3>, {v3, v3}}}.
Это описание можно отобразить графически, как показано на рис.3. На этом рисунке некоторые ребра отмечены стрелкой, а соответствующие им пары вершин в описании графа выделены угловыми скобками. Это связано с тем, что для некоторого произвольного ребра можно принимать или не принимать во внимание порядок расположения его концов.
Если этот порядок не существенен, то ребро называется неориентированным, в противном случае ребро называется ориентированным. Ориентированные ребра называются также дугами.
Рис. 3
Для ориентированного ребра определены понятия начальной и конечной вершины. Начальная вершина записывается в начале пары вершин, определяющих дугу, а конечная – в конце. Так, на рис.3 ребра <v5, v1> и <v2, v3> являются дугами. Они представлены упорядоченными парами вершин и в связи с этим обозначены также, как обозначаются упорядоченные множества.
Ребра {v1, v3}, {v3, v4} неориентированы. Для любого неориентированного ребра полагают, что {vi, vj} = {vj, vi}. Ребро {vi, vi} называется петлей. На рис.3 имеем петлю {v3, v3}. Петли обычно неориентированы.
Граф, у которого все ребра неориентированы, называется неориентированным.
Граф, у которого все ребра ориентированы, называется ориентированным или орграфом.
Иногда удобно преобразовывать неориентированный граф в ориентированный – заменой каждого неориентированного ребра парой ориентированных ребер с противоположной ориентацией.
На рис.3 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.
Некоторые вершину графа G могут не войти в список пар. Такие вершины называются изолированными. В рассмотренном примере это вершина v6. Граф, у которого все вершины изолированы, называется нуль-графом. Множество ребер такого графа пусто.
Антиподом нуль-графа является полный граф. Ребрами полного графа являются все возможные пары его вершин.
Как в случае ориентированного графа, так и в случае неориентированного, говорят, что ребро инцидентно паре определяющих его вершин.
Одной и той же паре вершин можно поставить в соответствии множество инцидентных ребер. Такие ребра называются кранными. Так, на рис.4 представлены различные пары вершин (vi, vj), инцидентных трем различным ребрам u1, u2, u3. Одно из них направлено, а два – нет.
Рис. 4
Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так, граф приведенный на рис.3, плоским не является, а на рис.4 – плоский.
Если граф G представлен конечным множеством ребер, то он называется конечным, независимо от числа вершин. В противном случае - бесконечный.
Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (G) графа G и все ребра U являются ребрами G. Частным, но важным типом частичных графов являются подграфы.
Пусть А – подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами – все ребра из G, оба конца которых лежат в А.
Для любой части G графа определена дополнительная часть G (дополнение), состоящая из всех тех ребер, которые не принадлежат G, и всех инцидентных им вершин.
Например, граф G на рис.5 неполный. А проведенные недостающие ребра составляют граф дополнение G рис.6.
Рис. 5 Рис. 6
Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Обозначать степени вершин v1, v2, v3 будем так: δ (v1), δ (v2), δ (v3) и т.п.
У графа на рис.7 δ (v1) = 1; δ (v2) = 2. У графа на рис. 8 степени всех вершин равны нулю.
Рис. 7 Рис. 8
При решении задач и доказательстве теорем использовались разные способы задания графов. На рисунках граф изображался с помощью точек (крутков, квадратиков) и отрезков, соединяющих пары точек. Можно граф представить специальной таблицей. Пользуются еще матричным представлением графа. Выбирают то представление или способ, который удобнее и нагляднее при рассмотрении конкретного вопроса.
Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов. Ниже рассматриваются две такие матричные формы и несколько нестандартных представлений, которые наиболее широко используются в алгоритмах на графах.
Пусть имеем граф G (V, U). Его матрицей смежности называется квадратная матрица (аi, j) порядка n2, где n – число вершин, а аi, j – число ребер, инцидентных вершинам vi и vj. Если граф не имеет кратных ребер, то аi, j = 1, когда vi и vj смежные, и аi, j = 0, когда vi и vj не смежные. Если граф не имеет петель, то все его диагональные элементы равны нулю.
Рассмотрим примеры. На рис. 9 изображены три неориентированных графа. В первом случае (рис.9а) имеем граф без петель и без кратных ребер. Во втором случае (рис.9б) имеем кратные ребра. В третьем случае (рис.9в) в вершинах v1 и v4 имеются петли.
а б в
Рис. 9
Соответствующие этим трем случаям матрицы смежности представлены ниже:
а) б) в)
Для неориентированного графа матрица смежности является симметрической. Для ориентированного графа матрица смежности симметрической, вообще говоря, не является.
Матрицей инциденций неориентированного графа, называется матрица (bi,j) размера n · m, где n – число вершин, а m – число ребер, построенная по правилу
Соответствующие рис.9б матрицы инциденций представлены ниже.
Примечание: для графа на рис. 9б приняты следующие обозначения ребер: Х1 = (v1, v2)1, Х2 = (v1, v2)2, Х3 = (v1, v4)1, Х4 = (v1, v4)2, Х5 = (v1, v4)3, Х6 = (v2, v4), Х7 = (v3, v2).
Матрица инциденций неориентированного графа обладает следующими очевидными свойствами:
1) в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра;
2) если в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных – по две.
Матрицей инциденций ориентированного графа называется матрица (bi, j) размера n · m, где n – число вершин, а m – число ребер, построенная по правилу
Рассмотрим, например, граф, изображенный на рис.10.
Рис. 10
Построенная в соответствии с описанным правилом матрица инциденций этого графа имеет вид
Примечание: для графа на рис.10 приняты следующие обозначения дуг: Х1 = (v1, v2), Х2 = (v1, v3), Х3 = (v3, v2), Х4 = (v3, v4), Х5 = (v5, v4), Х6 = (v5, v6), Х7 = (v6, v5).
Ориентированный граф, как правило, петель не содержит. Его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра.
Задачи, возникающие на практике, приводят к разного вида операциям над матрицами. Рассмотрим некоторые из них.
Пусть система авиалиний между городами Х1, Х2, Х3 одной страны и городами У1 и У2 другой страны задается подмножеством пар: (Х1, У1), (Х1, У2), (Х2, У1), (Х2, У2), (Х3, У2), т.е. множеством ребер соответствующего графа. Система связи между этими же городами водным транспортом задается другим подмножеством пар: (Х1, У1), (Х2, У1), (Х2, У2), (Х3, У1). Кроме этого, для каждой пары городов (Хi, Уj). Известно число различных водных и авиамаршрутов. Эти числа можно проставить над ребрами на рисунке графа или зафиксировать с помощью двух матриц одинакового порядка:
У1 У2 У1 У2
Х1 4 1 Х1 2 0
А = Х2 2 6 В = Х2 1 3
Х3 0 4 Х3 2 0
Требуется определить, сколькими различными способами с помощью воздушного или водного транспорта можно попасть из каждого города одной страны в каждый город другой страны.
Естественно, что для этого достаточно сложить соответствующие элементы матриц А и В. Ответ можно записать с помощью новой матрицы того же порядка:
У1 У2
Х1 6 1
С = Х2 3 9
Х3 2 4
В общем случае операцию сложения двух матриц можно записать так: если А = (аi,j) и В = (bi,j) – матрицы одного порядка, то матрица С = А + В = (Сi,j), где Сi,j = аi,j + bi,j.
Рассмотрим еще одну задачу. Пусть в каких-то трех странах выделены некоторые города, связанные с транспортом четырех видов: воздушным, железнодорожным, водным и автобусным. Схема транспортных связей между городами Х1 и Х2, принадлежащими первой стране, и городами У1, У2, У3, принадлежащими второй стране, зафиксирована матрицей А, где аi,j показывает на число видов транспорта, соединяющих города Хi и Уi. Аналогичная схема транспортных связей между городами У1, У2, У3, принадлежащими второй стране, и городами Z1, Z2, принадлежащим третьей стране, представлена матрицей В. Какие конкретно виды транспорта связывают пары городов, нас не интересует. Города первой и третьей стран непосредственных связей не имеют.
У1 У2 У3 Z1 Z2
А = Х1 4 0 2 У1 2 1
Х2 2 3 1 В = У2 0 3
У3 3 0
Требуется подсчитать число различных маршрутов от каждого из городов первой страны в каждый из городов третьей страны, проходящих через вторую страну.
Если нарисовать соответствующую схему, то решить задачу не трудно, попробуем решить матричным методом.
Таким образом, по заданным матрицам А и В требуется определить элементы сi,j матрицы С:
Z1 Z2
C = Х1 С11 С12
Х2 С21 С22
Рассуждения определяют матрицу С и алгоритм нахождения элементов сi,j, а именно
Z1 Z2
C = Х1 (а11в11 + а12в21 + а13в31 а11в12 + а12в22 + а13в32
Х2 (а21в11 + а22в21 + а23в31 а21в12 + а22в22 + а23в32
Z1 Z2
C = Х1 14 4
Х2 7 11
Рассмотренная задача убеждает в целесообразности введения еще одной операции над матрицами. Эту операцию принято называть операцией умножения матриц.
Если С = АВ, то элементы матрицы С определяются следующей формулой:
сi,j = ai1в1j + ai2в2j + ai3в3j + … + ainвnj
Таким образом, элемент сi,j образуется из элементов i-й строки матрицы А и элементов j-го столбца матрицы В.
Следует обратить внимание на следующие два факта:
1) операция умножения
матрицы А на матрицу В
2) если матрица А имеет порядок (m x n), а матрица В – порядок (n x r), то матрица – произведение С = АВ имеет порядок (n x m).
Рассмотрим некоторые основные операции, производимые над графами.
Операцией добавления к графу G = <V, U> вершины а образуется граф <V u {a}, U>.
Операцией добавления дуги (а, в) к графу G состоит в образовании графа <V u {a, в), U u {(а, в)}>. При операции удаления дуги, получаем <V, U \ {(а, в)}>. Операции удаления вершины заключается в удалении вершины Vi вместе с инцидентными ей дугами: <V\{Vi}, U \ {(Vj Vk) Vj = Vi или Vk = Vi}>. Операция отождествления вершин (в случае, когда Vi и Vj соединены дугой, операцию называют стягиванием дуги (ViVj).
Пример:
Рис. 11
Из графа G, добавлением вершины 5 образуется граф G1, добавлением дуги (3, 1) – G2, удалением дуги (3, 2) – G3, удалением вершины 2 – G4, отождествлением вершин 1 и 4 – G5 , стягиванием дуги (2, 3) – G6.
Добавлением графа без петель G = <V, U> называется граф = <V, V2 \ (U u i av)>.
Рис. 12
Объединением G1 u G2 называется граф <V1 u V2, U1 u U2>.
Если V1 ∩ V2 ≠ Ø, то пересечением G1 ∩ G2 называется граф <V1 ∩ V2, U1 ∩ U2 >.
Кольцевой суммой G1 + G2, называется граф <V1 u V2, (U1 \ U2) u (U2 \ U2).
Соединением G1 + G2 называется <V1 u V2, U1 u U2 u {[Vi, Vj] | Vi є V2, Vi ≠ Vj}>.
Произведением G1 x G2 называется граф <V1 x V2, U>.
Композицией G1 [G2] называется граф <V1 x V2, U>, в котором ((V1j, V1j), (Vj2, Vj2)) є U, если 1) (Vj1, Vj2) є U1; 2) Vi1 = Vi2, (Vj1, Vj2) є U2.
Рассмотрим специальный класс графов, имеющий важное практическое значение, представители которого именуются деревьями.
Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево не имеет петель и кратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов.
Рис. 14 Рис. 15
Пример дерева показан на рис.14, здесь же показаны висячие вершины, на рисунке они выделены закрашенными кружками (вершина дерева, степень которой равна единице, называется висячей вершиной).
Пример леса показан на рис.15.
Постройте какое-нибудь дерево с пятью вершинами и подсчитайте число ребер в полученном графе. Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра.
Теорема: дерево с n вершинами имеет n-1 ребро.
Для того, чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трех деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с n вершинами можно получить n деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить n-1 ребро из дерева Г. Итак, действительно, в дереве с n вершинами n-1 ребро.
Задача. Проводится эксперимент, при котором морскую свинку пускают в лабиринт (рис.16). Сколькими способами она может попасть к пище, если она ни в один тупик не заходит более одного раза, причем, попав в тупик, возвращается на перекресток, с которого свернула в этот тупик. Нарисуйте дерево всевозможных маршрутов морской свинки к пище.
Рис. 16
Ответ: 8 способами
Рис. 17
1.2. Раскраска графов
Пусть G = <V, U> - нефграф без петель.
Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если (Vi, Vj)-дуга, то вершины Vi, Vj имеют различные цвета. Хроматическим числом Х (G) графа G называется минимальное число цветов, требующиеся для раскраски G (рис. )
Пример. Так как в полном графе Gn любые две различные вершины связаны ребром, то Х (Gn) = n.
Многие практические задачи сводятся к построению раскрасок графов.
Пример 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. Построим граф G, вершины которого биективно соответствуют лекциям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно Х (G).
Пример 2. Рассмотрим граф G, вершины которого – страны, а ребра соединяют страны, имеющие общую границу. Число Х (G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.
Пример. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводника, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами – проводники.
Неорграф G называется бихроматическим, если Х (G) = 2. Неорграф G = <V, U> называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {V1, V2} концы любого ребра принадлежат разным частям разбиения.
Примером служит задача «Три дома, три колодца».
Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным.
1. Произвольная вершина V1 графа G принимает цвет 1.
2. Если вершины V1, …, Vi раскрашены l цветами е, 2, … е, е ≤ i, то новой произвольно взятой вершине Vi+1 припишем минимальный цвет, не использованный при раскраске вершин из множества {Vj | ρ (Vi+1, Vj) = 1, j < i}.
Для некоторых классов графов последовательная раскраска является минимальной. В общем случае это не так.
Все двудольные графы бихроматические, Х (G) = 2.
Пример:
бихроматический двудольный
Любой бихроматический граф является двудольным.
Теорема: для того, чтобы граф был бихроматическим, необходимо и достаточно, чтобы он был связным и не содержал элементарных циклов нечетной длины.
Дано: G – бихромат. граф
Док-ть: связный и не содержит циклов нечетной длины
Док-во (от противного)
Пусть граф содержит циклический элемент
Х = 3, но G – бихромат – противоречие.
Обратная теорема:
Дано: G – связный, не содержит циклов нечет. длины
Док-ть: Х (G) = 2
Док-во:
1) рассм. связный граф, который не имеет циклов
2) граф, содержит циклы четной длины
Глава 2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ НА ФАКУЛЬТАТИВНЫХ ЗАНЯТИЯХ В ШКОЛЕ
2.1. Роль факультативных занятий
Для правильного понимания того, как наладить наконец математические факультативы, необходимо вспомнить об их возникновении.
Еще на рубеже XIX и ХХ вв. некоторые педагоги поняли, что преподавание в общеобразовательной школе какого-либо предмета по обязательной единой общегосударственной программе становится существенно более успешным, если его дополнить циклом необязательных для учащихся, предназначенных только для желающих, внепрограммных групповых занятий.
Такие занятия должны были прежде всего учитывать «местные условия», а именно: реальные и потенциальные запросы и интересы конкретного количества учащихся данного класса, реальные возможности конкретного учителя вызвать и развить интерес учащихся к важным аспектам данного предмета, не охваченным обязательной программой.
Так возникла идея факультативных занятий в школе. Из толкового словаря Д.И.Ушакова: факультативный – необязательный, предоставленный собственному выбору.
«Влиятельность, воспитательность общеобразовательной школы, - писал в 1901 г. видный русский педагог Петр Федорович Каптерев, - ее значение в народной жизни и развитии культуры будут очень много зависеть от того, как будут поставлены факультативные занятия… на единообразной обязательности далеко не уедешь».
Учителя-энтузиасты дореволюционной и советской школы стали создавать для учащихся факультативные предметные семинары, они получили название, заимствованное из общественной жизни: кружки. Школьные кружки были созданы также при университетах и других вузах.
Опыт многих педагогов показал, что именно в предметном кружке возникает особенно благоприятная атмосфера для воспитания у школьников увлеченности предметом, энтузиазма, инициативы.
Важной вехой в истории советской школы был 1966 г., когда постановление ЦК КПСС и Совета Министров СССР «О мерах дальнейшего улучшения работы средней общеобразовательной школы» рекомендовало всем школам проведение в VII-Х классах факультативных занятий «для углубления знаний учащихся, для развития их интересов, способностей». Впервые все работники просвещения осознали, что такие занятия столь же важны, как и уроки по обязательной программе.
По существу в то время, в условиях единства средней общеобразовательной школы, единства системы среднего образования, факультативные занятия являлись единственной формой дифференцированного обучения.
В настоящее время факультативные занятия проводятся в школе наряду с другими формами дифференцированного обучения (уровневой и профильной дифференциацией). Часы на их проведение входят в варьируемую часть базисного учебного плана, в его школьный компонент.
Факультативные занятия организуются на добровольной основе, учащиеся выбирают курсы, которые они будут изучать, исходя из своих интересов и способностей к тому или иному предмету или виду деятельности.
Значение факультативных занятий состоит в том, что они позволяют:
- развивать склонности
и способности учащихся, давая
им соответствующую
- удовлетворять интересы учащихся;
- повышать качество
подготовки учащихся к
- развивать творческие способности учащихся, их самостоятельность;
- знакомить учащихся с современными достижениями науки и техники;
- формировать у учащихся общеучебные умения: готовить доклады и представлять их, выполнять рефераты, работать в группе, умение работать с информацией;
- способствовать
профессиональной ориентации
На сегодняшний день разработана система факультативных курсов, в которой условно можно выделить три группы:
1. Курсы повышенного
уровня, тесно связанные с основным
курсом математики. Их основная
цель – углубить знания, полученные
учащимися на уроках. Данные курсы
сочетают теоретическую и
2. Курсы прикладной математики, цель которых – познакомить учащихся с важнейшими путями и методами использования достижений математической науки на практике и развивать их интерес к развитию современной математической науке.
3. Спецкурсы, на
которых более глубоко
Некоторые факультативные курсы изучаются в течение одного года, другие – в течение двух-трех лет. Однако в последнем случае программы каждого года автономны и ученик может начать заниматься данным курсом в любом году.
Минимальная наполняемость группы, с которой могут проводиться факультативные занятия, - 10 человек. В сельских малокомплектных школах разрешено проводить факультативные занятия при меньшем составе группы, в этих школах в группу могут быть собраны учащиеся из разных классов.