Дискретка опред шпоры

Автоморфизм-изоморфизм : ϕ:Ƣ→~Ƣ Алгебра система-Ƣ=<А,Σ> не пустое мн-о А, где каждому предикат/функц символу из Σ поставлен в соотв. n-мест.предикат,опред.на мн-ве А; Бинарное отношение –двухместное отношение; Булева фун-ия- Е={0,1} . Фун-ия f(x1..xn) опр на Е^2 и приним значения на мн-ве Е . Взвешенное расст-обознач. ρw(a,b) м/у верш. a и b назыв мин из весов (a,b)маршр. Взвешенный эксц.- ew(a) назыв число ew(a)=max{ρw(a,b)|bϵM}; Взвешенный центр вершины назыв верш,для кот ew(a)=min{ew(b)|bϵM}; Гамитоновый граф-если в нем имеется простой цикл,содер каждую вершину этого графа; Гамитоновая цепь – назыв простая цепь , содер все верш графа; Гомоморфизм графа- ϕ :M ↔ M’ : (a,b)ϵR, то (ϕ(а), ϕ(в))ϵR’ ; Грани(<A,≤> BϵA): aϵA верх(нижн) грань мн-ва В:b<=(>=) a ∀bϵB; aϵA-точн верх(нижн) грань мн В: sup B если а-наим(наиб) из верх(нижн) граней; Группоид-Ƣ-сигнатуры Σ{f} мю(f)=2(2-x мест опер.) →подгруппа,если x,y,z:( x*y)*z =x*(y*z) →моноид, если сущ. еϵА:е*х=х*е=х→группой,если сущ x^-1:x*x^-1=x^-1*x=e→абилевой-x*y=y*x; Дерево-связный неор-й граф без циклов; Диаметр графа-max среди всех е(эксцентриситетов) : d(G)= max{e(a) |aϵM}; Дополн. графа без петель :=<M,M^2\ (RUid M)> ; Изморфные системы-если сущ изоморфизм Ƣ→~ɮ; Изоморфизм: ϕ : Ƣ→ɮ сюръек. мономорфизм , для кот ϕ^-1 гомоморфизм - ϕ:Ƣ→~ ɮ; Инъективная фун- ∀x1,x2ϵобл.опр : x1<>x2 ⇒f(x1)<>f(x2); Кардинал-мощность мн-ва; Класс экви эл х- Е(х)={у|хЕу} – Е классы ; Контур ом называется путь(все дуги разл),если а1=аn+1; Кратные дуги-неск дуг исход из а вход в b ; Лес-неор.граф без циклов(ациклический); Линейный порядок-частичн. порядок назыв лин-ым ,если любые 2 эл-та сравнимы; Маршрут-пос-ть a1,u1a2…un,an+1 (a-верш , u дуги) явл маршрутом, если соед верш-ы a1…an+1 , если ui=(ai,ai+1);(a1,an+1) –маршр.; МАТРИЦЫ : Бинар отн:PϵAxB [P]=(pij) pij=1(ai,bj)ϵP и =0 (ai,bj)неϵP ; Матрица смежности: графа Ag=a(ij) порядка n : aij=1(ai,aj)ϵR и =0 (ai,aj)неϵR ; Матр инцидентности порядка n : B_G=(bij) : bij=1(uj исходит из ai) =-1 (uj заходит в ai не петля) =0 (в ост случаях) Множество всех фуе-ий из А в В: В^A={f|f:A→B} ; Модель –сист явл моделью,если ее сигнатура предик.; Мономорфизм-гомомрфизм, ϕ : Ƣ→ɮ кот явл иньъекцией; Мощность мн- ва-класс всех подмн-в экви мн-ву А |A|; Макс мин наиб наим: a-max(min) если для любых хϵА a<=(>=)x => x=a ; a-наиб(наим) , если x<=(>=)a для любых хϵА Мощность алг сист-мощность ее носителя; Мультиграф- G=<M,U,P> М-мн-во вершин, U-мн-во дуг,Р(инцидентор)-отнош.,кот соед М и U; N-местн алг операция: f:A^n→A; N-местн фун-ия: f:A^n→B y=f(x1,..,xn);

Неориент граф- если граф сост только из ребер (R-симметр); Обл.знач δ={x|(x,y)ϵP}; Обл.опр:ρ={y|(x,y)ϵP} Образ мн-ва Х: P(X)={y|(x,y)ϵP} ; при отобр f Хϵδf: {f(x)|xϵX} ; Обхват графа – min из длин циклов в графе; Ограничение отображ- f∩(Xxρf); Ориент граф-если есть такая дуга(a,b)ϵR , что (b,a)неϵ R;Отождествление вершин:1)удаление a и b 2)добав вершина a’ и дуги (a’,c) ,если (a,c)ϵR (b,c)ϵR и дуг (с,a’) , если ( c,a)ϵR (c,b)ϵR; Операции над графом: 1)объед=<MUM’,RUR’> 2)пересеч.: =<M∩M’, R∩R’> 3)кольцевая сумма=< M∩M’,R(+)R’> 4)соединение=< MUM’, RUR’U{[a,b]} |aϵM,bϵM’,a<>b>;5)прямое произвед= <MxM’,R>: ((a1,b1)(a2,b2))ϵR ⇔ a1=a2ᴧ(b1,b2)ϵR’ v b1=b2ᴧ(a1,a2)ϵR; Переферийная вершина, если e(a)=d(g) (эксцинтр=диаметру) ; Подалгебра : если Σ функц,то подсист A алгебры B подалг; Подмодель--//- Σ предикат. Подграф: 1)M’ϵM 2) R’=R∩(M’)^2 ; Полустепень захода вершины-назыв число дуг, кот заходят в вершину а; ; Полустепень изхода вершины-кол-во дуг ,исход из а; Порядки: P-предпорядок,есди Р-рефл и транзит;РϵА²-частич порядок,если Р-рефл,транз и антисимм;Частич порядок-Линейный-если любые 2 эл-та сравнимы ; Полный порядок-линейный порядок , каждое не пустое подмн мн А имеет наим эл-т Произвед бинар отнош: P1◦P2={(x,y)|xϵA,yϵC ∃ zϵB : (x,z)ϵP1,(z,y)ϵP2 } композиция ; Путь-маршрут назыв путь,если все его дуги разл; Равномощные- если А экви В; Радиус графа- r(G)=min{e(a)|aϵM} ; Решетка-частично упорядоч мн-во Ƣ=<A,=> , в кот каждая пара эл-ов имеет inf и sup; Связный граф – в кот любые 2 верш соед маршр.; Сигнатура- совокупность предикат и функц символов с указанием их местности ; Если в ориент графе к любой (a,b) добавить (b,a) , то образ неориент графа,кот назыв Соответсвующим данному ориент графу , обознач F(G); Степень вершины а назыв число ребер инцедентных верш а,при этом петлю счит дважды(ск ребер исходит из а); Сюръекция- f:A→B если ρf(обл опр)=В; Термы-переменные и const из Σ . Если fϵΣ ? то f(t-терм)-также явл термом ; Фактор-мн-во: A/E={E(x)|xϵA}; Функция- fϵAxB .δf=A, ρfϵB : (x,y1)ϵf и (x,y2)ϵf , то y1=y2 ; Если δfϵA – Частич фун-ия; Часть графа-1)M’ϵM 2)R’ϵR∩(M’)² Центр графа-множество всех центральных вершин. Вершина центральная , если e(a)=r(G); Цепь-маршрут назыв цепью,если все ребра мар-та различны; Цикл-циклическая цепь (a₁=a_n+1) ; Эйлеров граф-граф, кот содержит цикл, в кот содерж все ребра мультиграфа; Экви мн-ва:А~В если ∃ f:A⟷B ; Р-отн экви., если P-рефлексивно и симметр и транзитивно; Эпиморфизм: гомомрфизм, ϕ : Ƣ→ɮ кот явл сюръекцией;