Большая коллекция шпор для МАТАНа (1 семестр 1 курс) - Математика - Скачать бесплатно
|
|некоторая функция, |биективное | |
|что существует U: xfu|(взаимооднозначное) | |
|и ugy |отображение ?:V1(V2, | |
|y=g[f(x)] |сохраняющее | |
|существует V: xfV |смежность, т.е. если | |
|=>U=V и Vgz =>y=z, |{v,w}ЄX1 <=> | |
|z=g[f(x)]. |{?(v),?(w)}ЄX2. | |
|УТВЕРЖДЕНИЕ: |Орграфы D1(V1,X1), | |
|композиция 2х |D2=(V2,X2) называются| |
|биективных функций – |изоморфными, если | |
|есть биективная |существует | |
|функция. ОПРЕДЕЛЕНИЕ:|отображение ?:V1(V2, | |
|тождественным |(v,w)ЄX1 <=> | |
|отображением |(?(v),?(w))ЄX2. | |
|множества Х в себя |Свойства изоморфных | |
|называется |графов: - если G1,G2 | |
|отображение e(инд.x):|– изоморфны и ?:V1(V2| |
|X(x, такое, что для |– для любого vЄV1, | |
|любых xЄX существует |?(v)=?(?(v)), - | |
|значение функции |m(G1)=m(G2), | |
|e(инд.x)(x)=x, |n(G1)=n(G2). Для | |
|foe(инд.x)=f, |орграфа свойства | |
|e(с.y)of=f. |аналогичны, для | |
|УТВЕРЖДЕНИЕ: |любого vЄV1, | |
|отображение f: X(Y |?(с.-)(v)=?(инд.-)(?(| |
|имеет обратное |v)) | |
| |, | |
|ОТНОШЕНИЕ ЧАСТИЧНОГО |?(с.+)(v)=?(с.+)(?(v)| |
|ПОРЯДКА |), m(D1)=m(D2), | |
|на множестве х, для |n(D1)=n(D2). Примеры | |
|которого 2 любые |изоморфных графов см.| |
|элементы сравнимы |на рисунке. | |
|называется отношением|УТВЕРЖДЕНИЕ: | |
|линейного порядка. |изоморфизм групп | |
|Любые x,yЄX либо x?y |является отношением | |
|либо y?x. |эквивалентности на | |
|Определение: говорят,|множестве | |
|что элемент х |графов или орграфов. | |
|покрывает элемент y, |ОПРЕДЕЛЕНИЕ: | |
|если x?y и |операцией по | |
|существует такое, что|разбиению дуги (u,v) | |
|x?z?y. |в орграфе D(v,x) | |
| |называется | |
|ДИАГРАММА ХАССЕ |операция, которая | |
|ПРИМЕРЫ: некое |состоит из удаления | |
|множество A={1,2,3} |добавления к V | |
|и его булеан |вешины w. Орграф D2 | |
|B(A)={Ш,{1},{2},{3}, |называется разбиением| |
|{1,2}, |орграфа D1 | |
|{1,3}, {2,3}, |, если D2 получается | |
|{1,2,3}}=X. 1,2,3 |из D1 путем | |
|покрывают Ш. |последовательного | |
|Множество |применения интеграции| |
|Х={1,2,3,5,6,10,15,30|дуг. Орграфы | |
|}. y делится |D1,D2(G1,G2) | |
|нацель на х. |называются | |
|Диаграммы ХАССЕ на |гомеоморфными, если | |
|рисунке. |существует их | |
|Если порядок |подразделение, | |
|линейный, то просто |которое является | |
|линия будет. |изоморным. Если | |
|Определение: 2 |степени всех вершин | |
|частично |равны k, то граф | |
|упорядоченных |называется регулярным| |
|множества Х,Y |в степени k. Граф | |
|называются |исходящий из 1 | |
|изоморфными, если |вершины называется | |
|существует биективная|тривиальным. | |
|функция, ?*Х(Y, |Двудольным называется| |
|сохраняющая частичный|граф G(V,X), | |
|порядок, т.е. для |такой, что он разбит | |
|любых x,yЄX, x?y => |V1,V2(v1Uv2=v, | |
|?(x)??(y). |v1?v2?Ш), | |
| |каждое ребро | |
|СРАВНЕНИЕ МНОЖЕСТВ |инцедентно вершине из| |
|ОПРЕДЕЛЕНИЕ: |v1 и v2. | |
|множества А и В | | |
|называются | | |
|равномощными, если | | |
|между АиВ существуют | | |
|взаимно однозначные | | |
|соответствия. 1. A(B,| | |
||A|=|B|. УТВЕРЖДЕНИЕ:| | |
|отношение | | |
|равномощности | | |
|множеств является | | |
|отношением | | |
|эквивалентности. | | |
|Реплексивность – | | |
|можно установить | | |
|соответствие – сам с | | |
|собой. Симметрия – | | |
|хоть так, хоть эдак. | | |
|СЛУЧАЙ 1: АиВ | | |
|конечное множество: | | |
|утверждение: | | |
|множества А и В | | |
|равномощны т. и т.т.,| | |
|к. количество | | |
|элементов в А равно | | |
|количеству элементов | | |
|в В. Докажем: | | |
|допустим 2 множества | | |
|имеют одинаковые | | |
|элементы, имеют | | |
|одинаковые индексы | | |
|соответствующих друг | | |
|другу значений. | | |
|Множества равномощны.| | |
|Обратно: допустим | | |
|множества равномощны | | |
|=> существуют взаимно| | |
|однозначные | | |
|соответствия. | | |
|Мощность равна | | |
|количеству элементов,| | |
|для конечных | | |
|множеств. СЛУЧАЙ2: | | |
|бесконечное | | |
|множество: | | |
|N={1,2,3..}. Пример: | | |
|множество всех | | |
|натуральных чисел. И | | |
|множество всех четных| | |
|чисел: M={2,3,4..}. |
|
