Министерство образования и науки рф
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«КАБАРДИНО-БАЛКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Х.М. БЕРБЕКОВА»
МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ
Карданова Милана Беслановна
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
«О - однородных расширениях частичных геометрий с большим»
Научный руководитель:
к.ф.-м.н.,доцент каф. ГиВА………………………………………….… Нирова М.С.
Рецензент:
к.ф.-м.н., доцент каф.
вычислит.математики………………………………………………………...…. Кудаев В.Ч.
Допущена к защите «____»_________________2014г.
Зав.каф. ГиВА
д.ф.-м.н., профессор……………………………………………………………... Журтов А.Х.
Нальчик 2014г.
Содержание
Введение………………………………………………………………………….3
§ 1. Принятые обозначения и определения …………………………………….
§ 2. Об однородных расширениях частичных геометрий……………….……
Предварительные результаты…………………………………………….
Случай ……………………………………………………………….
Сильно - однородные геометрии………………………………….
§ 3.…………………………………...
Заключение…………………………………………………………………………
Список литературы………………………………………………………………
§ 1. Принятые обозначения и определения .
Граф G – это пара множеств , где- множество вершин, а- множество ребер. Вершины и рёбра графа называются его элементами.
Число вершин графа G называется его порядком и обозначается через . Если, тоG называют - графом.
Говорят, что две вершины и смежны, если множество является ребром, и не смежны в противном случае. Если - ребро, то вершиныи называют его концами.Два ребра ребра называются смежными, если они имеют общий конец.
Вершина и реброназываютсяинцидентными, если является концом ребра( т.е.), и не инцидентными в противном случае.
Множество всех вершин графа G , смежных с вершиной называетсяокрестностью вершины и обозначается через.
Граф G называется полным, если любые две его вершины смежны , т.е. . Полный граф порядкаобозначают символомчисло рёбер в нём равно
Граф G называется пустым, если в нём нет рёбер. Пустой граф порядка обозначается через.
Граф G называется двудольным, если множество его вершин разбито на части (доли ) так, что концы каждого ребра принадлежат разным частям (долям). Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным .
Полный двудольный граф, доли которого состоят из и извершин, обозначается.
Аналогично двудольным определяются -дольный и полный-дольный графы для.
Легко подсчитать число всех графов с фиксированным множеством вершин . Эти графы различаются своими рёбрами, и поэтому их число равно количеству подмножеств в, т.е.
, где .
Мультиграф – это пара , где- множество вершин, а- семейство множеств множества(рёбер).
Употребление термина «семейства» вместо «множество »означает, что элементы множества могут вповторятся, т.е. допускаются кратные рёбра.
Петли – это рёбра соединяющие вершину саму с собой. Если допускаются петли и кратные рёбра, получаем псевдограф.
Ориентированный граф (или орграф) – это пара , где- множество вершин,- множество ориентированных рёбер, которые называются дугами,. Если- дуга, то вершиныиназываются её началом и концом.
Направленный граф – это орграф, не имеющий симметричных (т.е. дуг вида и) пар ориентированных рёбер.
Два графа G и Н изоморфны , если между их множеством вершин существует взаимно однозначное соответствие, сохраняющие смежность.
Изоморфизм есть отношение эквивалентности на графах.
Подграфом G называется граф, у которого все вершины и рёбра принадлежат G .
Остовый граф – это подграф графа G, содержащий все его вершины (т.е. ). Если множество вершин подграфа Н есть, а множество его рёбер совпадает с множеством всех рёбер графаG, оба конца которых принадлежат ,то Н называетсяподграфом, порождённым множеством , и обозначается через.
Матрицей смежности графа G с множеством вершин называется матрица,(т.е.), в которой элементравен числу рёбер вG , соединяющих и.
Удаление вершины или ребра, а также переход к другому подграфу – это операции, с помощью которых можно из имеющегося графа получать другие графы с меньшим числом элементов. Известны так же операции позволяющие увеличить число элементов графа. Например, операция добавления ребра: если вершины ине смежны, то можно определить граф, где. Он получается из графаGдобавлением ребра.
Граф называется объединением графови, еслии(или). Объединениеназывается дизъюнктивным, если, т.е. никакие два из объединяемых графов не должны иметь общих вершин .
Говорят, что графы исоединены (обозначается), если состоит изи всех рёбер соединяющихи. В частности ,, где
и .
Произведением графов и (обозначается ) называется граф, для которого- декартово произведения множеств вершин исходных графов, а определяется так: вершины исмежны вG тогда и только тогда, когда или , аисмежны в, или, аисмежны в.
С помощью операции произведения вводится важный класс графов - -мерные кубы. Он определяется рекуррентно:
.
- это граф порядка , вершины которого можно представить- векторами длинытаким образом, что две вершины будут смежны тогда и только тогда, когда соответствующие векторы различаются ровно в одной координате. Поскольку каждая вершина-мерного куба инцидентна- ребрам, то число его рёбер равно.
Ещё одна важная операция – отождествление (или слияние) вершин. Пусть идве вершины графаG, . К графу присоединим новую вершину, соединив её ребром с каждой из вершин, входящих в объединение окружений вершинив графеG . Говорят, что построенный граф получается из графа G отождествлением вершин и
Граф G называется стягиваемым к графу Н, если Н получается из G в результате некоторой последовательности стягивания рёбер.
Например, граф Петерсена стягиваем к и стало быть к любомус. Любой непустой связный граф отличный отстягиваем к. Но уже не любой связный граф стягивается к. Например, простая цепне стягивается к. Поэтому возникает параметр- максимум порядков полных графов к которым стягивается графG. Параметр называетсяХадвигера графа G .
Степенью вершины называют количество входящих в вершину рёбер.
Путём в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром.
Циклом называют путь, в котором первая и последняя вершины соединены ребром.
Деревом называют связный граф без циклов.
Расстоянием между вершинамииграфа Г называется длина кратчайшей простой цепи, соединяющей их; если ине соединены, то полагаем
Степенью вершины в графе Г – обозначается или- называется число рёбер, инцидентных
Непустое множество А вместе с заданной на нем бинарной операцией () образует группу, если выполнены следующие четыре аксиомы:
Аксиома 1 (замыкание). Для любых двух элементов а и в, принадлежащих множеству А, элемент а в принадлежит А.
Аксиома 2(ассоциативности) Для любых трёх элементов а,в,с, принадлежащих множеству А, справедливо равенство а(вс)=(ав) с.
Аксиома 3 (тождественности). В множестве А существует такой элемент е, что еа=ае=а, для всех элементов а из А.
Аксиома 4 (обращения). Если выполняется аксиома 3, то для любого элемента а, принадлежащего множеству А, существует элемент, обозначаемый , такой, что.
Взаимно однозначное отображение конечного множества на себя называется подстановкой.
Автоморфизмом графа Г называется изоморфизм графа Г на себя. Таким образом, каждый автоморфизм графа Г есть подстановка множества вершинV, сохраняющая смежность.
Неориентированный - вершинный граф, в котором степени всех вершин равны, а каждое ребро принадлежит точнотреугольникам, называетсярёберно регулярным с параметрами . Положим. Сильно регулярным графом с параметраминазывается рёберно регулярный граф с соответствующими параметрами, в котором пересечение окрестностей любых несмежных вершин содержащих точновершин .
Пара , из, называетсяфлагом, если точка принадлежит блоку, иантифлагом в противном случае. Если является антифлагом, то черезобозначим число точек в, коллинеарных. Геометрия называется–однородной (– натуральное число), если для любого антифлагачислоравно 0 или, исильно - однородной, если это число всегда равно .
Если есть такая геометрия точек и прямых, что каждая прямая имеет ровноточку, каждая точка лежит ровно напрямойиявляется сильно -однороднойто тогданазывается - частичной геометрией порядка (для краткостиили даже). Связное расширение семейства частичных геометрийобозначается как(или даже).
Блоки геометрии называютсяпрямыми, если различные блоки пересекаются не более чем в одной точке.
Вычет геометриив точке – это геометрия ранга 2, где– множество всех точек, коллинеарных, и. Пусть- семейство геометрий ранга 2, и всякий вычетлежит в. Тогда говорят, что S являетсярасширением .
Геометрия называетсятреугольной, если для любых попарно коллинеарных точек найдется блок, содержащий все три точки.
Если - частичная геометрия, то двойственная геометрия, в которой каждая точка отождествляется с пучком проходящих через нее прямых, является частичной геометрией. Обобщенный четырехугольник- это частичная геометрия. Геометрияявляется сетью, аявляется 2-схемой с. Коклика из точек в точечном графе геометрии называется овоидом.