#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\begin_preamble
\usepackage{siunitx}
\usepackage{pgfplots}
\usepackage{listings}
\usepackage{multicol}
\sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}}
\DeclareMathOperator{\g}{g}
\DeclareMathOperator{\sled}{sled}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Cir}{Cir}
\DeclareMathOperator{\ecc}{ecc}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\diam}{diam}
\newcommand\euler{e}
\end_preamble
\use_default_options true
\begin_modules
enumitem
\end_modules
\maintain_unincluded_children false
\language slovene
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics xetex
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification false
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 1cm
\topmargin 1cm
\rightmargin 1cm
\bottommargin 2cm
\headheight 1cm
\headsep 1cm
\footskip 1cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style german
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
setlength{
\backslash
columnseprule}{0.2pt}
\backslash
begin{multicols}{2}
\end_layout
\end_inset
\end_layout
\begin_layout Standard
Največja stopnja
\begin_inset Formula $\Delta G$
\end_inset
, najmanjša
\begin_inset Formula $\delta G$
\end_inset
.
\end_layout
\begin_layout Standard
Rokovanje:
\begin_inset Formula $\sum_{v\in VG}\deg_{G}v=2\left|EG\right|$
\end_inset
.
\end_layout
\begin_layout Standard
Vsak graf ima sodo mnogo vozlišč lihe stopnje.
\end_layout
\begin_layout Standard
Presek/unija grafov je presek/unija njunih
\begin_inset Formula $V$
\end_inset
in
\begin_inset Formula $E$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $G\cup H$
\end_inset
je disjunktna unija grafov
\begin_inset Formula $\sim$
\end_inset
\begin_inset Formula $VG\cap VH=\emptyset$
\end_inset
.
\end_layout
\begin_layout Standard
Komplement grafa:
\begin_inset Formula $\overline{G}$
\end_inset
(obratna povezanost)
\end_layout
\begin_layout Standard
\begin_inset Formula $0\leq\left|EG\right|\leq{\left|VG\right| \choose 2}\quad\quad\quad$
\end_inset
Za padajoče
\begin_inset Formula $d_{i}$
\end_inset
velja:
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(d_{1},\dots d_{n}\right)$
\end_inset
graf
\begin_inset Formula $\Leftrightarrow\left(d_{2}-1,\dots,d_{d_{1}+1}-1,\dots,d_{n}\right)$
\end_inset
graf
\end_layout
\begin_layout Standard
Če je
\begin_inset Formula $AG$
\end_inset
matrika sosednosti,
\begin_inset Formula $\left(\left(AG\right)^{n}\right)_{i,j}$
\end_inset
pove št.
\begin_inset Formula $i,j-$
\end_inset
poti.
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
\text{Število trikotnikov: }\frac{\sled\left(\left(AG\right)^{3}\right)}{2\cdot3}
\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\left|EK_{n}\right|={n \choose 2}$
\end_inset
,
\begin_inset Formula ${n \choose k}=\frac{n!}{k!\left(n-k\right)!}$
\end_inset
\end_layout
\begin_layout Paragraph
Sprehod
\end_layout
\begin_layout Standard
je zaporedje vozlišč, ki so verižno povezana.
\end_layout
\begin_layout Standard
Dolžina sprehoda je število prehojenih povezav.
\end_layout
\begin_layout Standard
Sklenjen sprehod dolžine
\begin_inset Formula $k$
\end_inset
:
\begin_inset Formula $v_{0}=v_{k}$
\end_inset
\end_layout
\begin_layout Standard
Enostaven sprehod ima disjunktna vozlišča razen
\begin_inset Formula $\left(v_{0},v_{k}\right)$
\end_inset
.
\end_layout
\begin_layout Standard
Pot v grafu: podgraf
\begin_inset Formula $P_{k}$
\end_inset
\begin_inset Formula $\sim$
\end_inset
enostaven nesklenjen sprehod.
\end_layout
\begin_layout Paragraph
Cikel
\end_layout
\begin_layout Standard
podgraf, ki je enostaven sklenjen sprehod dolžine
\begin_inset Formula $>3$
\end_inset
.
\end_layout
\begin_layout Standard
Če v
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $\exists$
\end_inset
dve različni
\begin_inset Formula $u,v-$
\end_inset
poti
\begin_inset Formula $\Leftrightarrow$
\end_inset
\begin_inset Formula $G$
\end_inset
premore cikel
\end_layout
\begin_layout Standard
Sklenjen sprehod lihe dolžine
\begin_inset Formula $\in G$
\end_inset
\begin_inset Formula $\Leftrightarrow$
\end_inset
lih cikel
\begin_inset Formula $\in G$
\end_inset
\end_layout
\begin_layout Paragraph
Povezanost
\end_layout
\begin_layout Standard
\begin_inset Formula $u,v$
\end_inset
sta v isti komponenti
\begin_inset Formula $\text{\ensuremath{\sim}}$
\end_inset
\begin_inset Formula $\text{\ensuremath{\exists}}$
\end_inset
\begin_inset Formula $u,v-$
\end_inset
pot
\end_layout
\begin_layout Standard
Število komponent grafa:
\begin_inset Formula $\Omega G$
\end_inset
.
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\sim\Omega G=1$
\end_inset
\end_layout
\begin_layout Standard
Komponenta je maksimalen povezan podgraf.
\end_layout
\begin_layout Standard
Premer:
\begin_inset Formula $\diam G=\max\left\{ d_{G}\left(v,u\right);\forall v,u\in VG\right\} $
\end_inset
\end_layout
\begin_layout Standard
Ekscentričnost:
\begin_inset Formula $\ecc_{G}u=max\left\{ d_{G}\left(u,x\right);\forall x\in VG\right\} $
\end_inset
\end_layout
\begin_layout Standard
Polmer:
\begin_inset Formula $\rad G=\min\left\{ \ecc u;\forall u\in VG\right\} $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\diam C_{n}=\rad C_{n}=\lfloor\frac{n}{2}\rfloor$
\end_inset
\end_layout
\begin_layout Standard
(Liha) ožina (
\begin_inset Formula $\g G$
\end_inset
) je dolžina najkrajšega (lihega) cikla.
\end_layout
\begin_layout Standard
Vsaj en od
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $\overline{G}$
\end_inset
je povezan.
\end_layout
\begin_layout Standard
Povezava
\begin_inset Formula $e$
\end_inset
je most
\begin_inset Formula $\Leftrightarrow$
\end_inset
\begin_inset Formula $\Omega\left(G-e\right)>\Omega G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $u$
\end_inset
je prerezno vozlišče
\begin_inset Formula $\Leftrightarrow$
\end_inset
\begin_inset Formula $\Omega\left(G-u\right)>\Omega G$
\end_inset
\end_layout
\begin_layout Standard
Za nepovezan
\begin_inset Formula $G$
\end_inset
velja
\begin_inset Formula $\diam\overline{G}\leq2$
\end_inset
\end_layout
\begin_layout Paragraph
Dvodelni
\end_layout
\begin_layout Standard
\begin_inset Formula $\sim V=A\cup B,A\cap B=\emptyset,\forall uv\in E:u\in A\oplus v\in A$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $K_{m,n}$
\end_inset
je poln dvodelni graf,
\begin_inset Formula $\left|A\right|=m$
\end_inset
,
\begin_inset Formula $\left|B\right|=n$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
dvodelen
\begin_inset Formula $\Leftrightarrow\forall$
\end_inset
komponenta
\begin_inset Formula $G$
\end_inset
dvodelna
\end_layout
\begin_layout Standard
Pot, sod cikel, hiperkocka so dvodelni, petersenov ni.
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
dvodelen
\begin_inset Formula $\Leftrightarrow G$
\end_inset
ne vsebuje lihega cikla.
\end_layout
\begin_layout Standard
Biparticija glede na parnost
\begin_inset Formula $d_{G}\left(u,x_{0}\right)$
\end_inset
,
\begin_inset Formula $x_{0}$
\end_inset
fiksen.
\end_layout
\begin_layout Standard
Dvodelen
\begin_inset Formula $k-$
\end_inset
regularen,
\begin_inset Formula $\left|E\right|\ge1\Rightarrow$
\end_inset
\begin_inset Formula $\left|A\right|=\left|B\right|$
\end_inset
.
Dokaz:
\begin_inset Formula $\sum_{u\in A}\deg u=\left|E\right|=\cancel{k}\left|A\right|=\cancel{k}\left|B\right|=\sum_{u\in B}\deg u$
\end_inset
\end_layout
\begin_layout Paragraph
Krožni
\end_layout
\begin_layout Standard
\begin_inset Formula $\Cir\left(n,\left\{ s_{1},\dots,s_{k}\right\} \right):\left|V\right|=n,$
\end_inset
množica preskokov
\end_layout
\begin_layout Standard
\begin_inset Formula $\Omega\Cir\left(n,\left\{ s,n-s\right\} \right)=\gcd\left\{ n,s\right\} $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $W_{n}$
\end_inset
(kolo) pa je cikel z univerzalnim vozliščem.
\end_layout
\begin_layout Paragraph
Homomorfizem
\end_layout
\begin_layout Standard
\begin_inset Formula $\varphi:VG\to VH$
\end_inset
slika povezave v povezave
\end_layout
\begin_layout Standard
Primer:
\begin_inset Formula $K_{2}$
\end_inset
je homomorfna slika
\begin_inset Formula $\forall$
\end_inset
bipartitnega grafa.
\end_layout
\begin_layout Standard
V povezavah in vozliščih surjektiven
\begin_inset Formula $hm\varphi$
\end_inset
je epimorfizem.
\end_layout
\begin_layout Standard
V vozliščih injektiven
\begin_inset Formula $hm\varphi$
\end_inset
je monomorfizem/vložitev.
\end_layout
\begin_layout Standard
Vložitev, ki ohranja razdalje, je izometrična.
\end_layout
\begin_layout Standard
Kompozitum homomorfizmov je spet homomorfizem.
\end_layout
\begin_layout Standard
Izomorfizem je bijektivni
\begin_inset Formula $hm\varphi$
\end_inset
s homomorfnim inverzom.
\end_layout
\begin_layout Standard
\begin_inset Formula $im\varphi$
\end_inset
\begin_inset Formula $f:VG\to VH$
\end_inset
\begin_inset Formula $\forall u,v\in VG:uv\in EG\Leftrightarrow fufv\in EH$
\end_inset
\end_layout
\begin_layout Standard
Nad množico vseh grafov
\begin_inset Formula $\mathcal{G}$
\end_inset
je izomorfizem (
\begin_inset Formula $\cong$
\end_inset
) ekv.
rel.
\end_layout
\begin_layout Standard
\begin_inset Formula $im\varphi$
\end_inset
\begin_inset Formula $G\to G$
\end_inset
je avtomorfizem.
\end_layout
\begin_layout Standard
\begin_inset Formula $\Aut G$
\end_inset
je grupa avtomorfizmov s komponiranjem.
\end_layout
\begin_layout Standard
\begin_inset Formula $\Aut K_{n}=\left\{ \pi\in S_{n}=\text{permutacije }n\text{ elementov}\right\} $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\Aut P_{n}=\left\{ \text{trivialni }id,f\left(i\right)=n-i-1\right\} $
\end_inset
,
\begin_inset Formula $\Aut G\cong\Aut\overline{G}$
\end_inset
\end_layout
\begin_layout Standard
Izomorfizem ohranja stopnje, št.
\begin_inset Formula $C_{4}$
\end_inset
, povezanost,
\begin_inset Formula $\left|EG\right|,\dots$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G\cong\overline{G}\Rightarrow\left|VG\right|\%4\in\left\{ 0,1\right\} $
\end_inset
\end_layout
\begin_layout Paragraph
Operacije
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
vpeti podgraf
\begin_inset Formula $G\Leftrightarrow\exists F\subseteq EG\ni:H=G-F$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
inducirani podgraf
\begin_inset Formula $G\Leftrightarrow\exists S\subseteq VG\ni:H=G-S$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
podgraf
\begin_inset Formula $G\Leftrightarrow\exists S\subseteq VG,F\subseteq EG\ni:H=\left(G-F\right)-S$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $uv=e\in EG$
\end_inset
.
\begin_inset Formula $G/e$
\end_inset
je skrčitev.
(identificiramo
\begin_inset Formula $u=v$
\end_inset
)
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
minor
\begin_inset Formula $G$
\end_inset
:
\begin_inset Formula $H=f_{1}...f_{k}G$
\end_inset
za
\begin_inset Formula $f_{i}$
\end_inset
skrčitev/odstranjevanje
\end_layout
\begin_layout Standard
\begin_inset Formula $VG^{+}e\coloneqq VG\cup\left\{ x_{e}\right\} $
\end_inset
,
\begin_inset Formula $EG^{+}e\coloneqq EG\setminus e\cup\left\{ x_{e}u,x_{e}v\right\} $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $VG^{+}e$
\end_inset
je subdivizija,
\begin_inset Formula $e\in EG$
\end_inset
.
Na
\begin_inset Formula $e$
\end_inset
dodamo vozlišče.
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
subdivizija
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $\Leftrightarrow H=G^{+}\left\{ e_{1},\dots,e_{k}\right\} ^{+}\left\{ f_{1}\dots f_{j}\right\} ^{+}\dots$
\end_inset
\end_layout
\begin_layout Standard
Stopnja vozlišč se s subdivizijo ne poveča.
\end_layout
\begin_layout Standard
Glajenje
\begin_inset Formula $G^{-}v$
\end_inset
,
\begin_inset Formula $v\in VG$
\end_inset
je obrat subdivizije.
\begin_inset Formula $\deg_{G}v=2$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
sta homeomorfna, če sta subdivizija istega grafa.
\end_layout
\begin_layout Standard
Kartezični produkt:
\begin_inset Formula $V\left(G\square H\right)\coloneqq VG\times VH$
\end_inset
,
\begin_inset Formula $E\left(G\square H\right)\coloneqq\left\{ \left\{ \left(g,h\right),\left(g',h'\right)\right\} ;g=g'\wedge hh'\in EH\vee h=h'\wedge gg'\in EG\right\} $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(\mathcal{G},\square\right)$
\end_inset
monoid, enota
\begin_inset Formula $K_{1}$
\end_inset
.
\begin_inset Formula $Q_{n}\cong Q_{n-1}\square K_{2}=Q_{n-2}\square K_{2}^{\square,2}$
\end_inset
\end_layout
\begin_layout Standard
Disjunktna unija:
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $H$
\end_inset
disjunktna.
\begin_inset Formula $V\left(G\cup H\right)\coloneqq VG\cup VH$
\end_inset
,
\begin_inset Formula $E\left(G\cup H\right)\coloneqq EG\cup EH$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G,H$
\end_inset
dvodelna
\begin_inset Formula $\Rightarrow G\square H$
\end_inset
dvodelen
\end_layout
\begin_layout Paragraph
\begin_inset Formula $k-$
\end_inset
povezan graf
\end_layout
\begin_layout Standard
ima
\begin_inset Formula $\geq k+1$
\end_inset
vozlišč in ne vsebuje prerezne množice moči
\begin_inset Formula $<k$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $X\subseteq VG$
\end_inset
je prerezna množica
\begin_inset Formula $\Leftrightarrow\Omega\left(G-X\right)>\Omega G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $Y\subseteq EG$
\end_inset
prerezna množica povezav
\begin_inset Formula $\Leftrightarrow\Omega\left(G-Y\right)>\Omega G$
\end_inset
\end_layout
\begin_layout Standard
Povezanost grafa:
\begin_inset Formula $\kappa G=\max k$
\end_inset
, da je
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $k-$
\end_inset
povezan.
Primeri:
\begin_inset Formula $\kappa K_{n}=n-1$
\end_inset
,
\begin_inset Formula $\kappa P_{n}=1$
\end_inset
,
\begin_inset Formula $\kappa C_{n}=2$
\end_inset
,
\begin_inset Formula $\kappa K_{n,m}=\min\left\{ n,m\right\} $
\end_inset
,
\begin_inset Formula $\kappa Q_{n}=n$
\end_inset
,
\begin_inset Formula $\kappa G\text{\ensuremath{\leq}}\delta G$
\end_inset
\end_layout
\begin_layout Standard
Izrek (Menger):
\begin_inset Formula $\left|VG\right|\geq k+1$
\end_inset
:
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $k-$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG,uv\not\in EG:\exists k$
\end_inset
notranje disjunktnih
\begin_inset Formula $u,v-$
\end_inset
poti
\end_layout
\begin_layout Standard
Graf je
\begin_inset Formula $k-$
\end_inset
povezan po povezavah, če ne vsebuje prerezne množice povezav moči
\begin_inset Formula $<k$
\end_inset
.
Povezanost grafa po povezavah:
\begin_inset Formula $\kappa'G=\max k$
\end_inset
, da je
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $k-$
\end_inset
povezan po povezavah.
Primeri:
\begin_inset Formula $\kappa'K_{n}=n-1$
\end_inset
,
\begin_inset Formula $\kappa'P_{n}=1$
\end_inset
,
\begin_inset Formula $\kappa'C_{n}=2$
\end_inset
\end_layout
\begin_layout Standard
Izrek (Menger'):
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $k-$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists k$
\end_inset
po povezavah disjunktnih
\begin_inset Formula $u,v-$
\end_inset
poti
\end_layout
\begin_layout Standard
\begin_inset Formula $\forall G\in\mathcal{G}:\kappa G\leq\kappa'G\leq\delta G$
\end_inset
\end_layout
\begin_layout Paragraph
Drevo
\end_layout
\begin_layout Standard
je povezan gozd.
Gozd je graf brez ciklov.
\end_layout
\begin_layout Standard
Drevo z vsaj dvema vozliščema premore dva lista.
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
hspace*{
\backslash
fill}
\end_layout
\end_inset
NTSE:
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
drevo
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists!u,v-$
\end_inset
pot
\begin_inset Formula $\Leftrightarrow\Omega G=1\wedge\forall e\in EG:e$
\end_inset
most
\begin_inset Formula $\Leftrightarrow\Omega G=1\wedge\left|EG\right|=\left|VG\right|-1$
\end_inset
\end_layout
\begin_layout Standard
Vpeto drevo grafa je vpet podgraf, ki je drevo.
\end_layout
\begin_layout Standard
\begin_inset Formula $\tau G\sim$
\end_inset
število vpetih dreves.
\begin_inset Formula $\Omega G=1\Leftrightarrow\tau G\geq1$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\forall e\in EG:\tau G=\tau\left(G-e\right)+\tau\left(G/e\right)$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
\text{\text{\text{Laplaceova matrika: }}}L\left(G\right)_{ij}=\begin{cases}
\deg_{G}v_{i} & ;i=j\\
-\left(\text{št. uv povezav}\right) & ;\text{drugače}
\end{cases}
\]
\end_inset
\end_layout
\begin_layout Standard
Izrek (Kirchoff): za
\begin_inset Formula $G$
\end_inset
povezan multigraf je
\begin_inset Formula $\forall i:\tau G=\det\left(LG\text{ brez \ensuremath{i}te vrstice in \ensuremath{i}tega stolpca}\right)$
\end_inset
.
\begin_inset Formula $\tau K_{n}=n^{n-2}$
\end_inset
\end_layout
\begin_layout Standard
Prüferjeva koda, če lahko linearno uredimo vozlišča: Ponavljaj, dokler
\begin_inset Formula $VG\not=\emptyset$
\end_inset
: vzemi prvi list, ga odstrani in v vektor dodaj njegovega soseda.
\end_layout
\begin_layout Standard
Blok je maksimalen povezan podgraf brez prereznih vozlišč.
\end_layout
\begin_layout Standard
\begin_inset Formula $\tau G=\tau B_{1}\cdot\cdots\cdot\tau B_{k}$
\end_inset
za bloke
\begin_inset Formula $\vec{B}$
\end_inset
grafa
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
end{multicols}
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
begin{multicols}{2}
\end_layout
\end_inset
\end_layout
\begin_layout Paragraph
Eulerjev
\end_layout
\begin_layout Standard
sprehod v m.grafu vsebuje vse povezave po enkrat.
\end_layout
\begin_layout Standard
Eulerjev obhod je sklenjen eulerjev sprehod.
\end_layout
\begin_layout Standard
Eulerjev graf premore eulerjev obhod.
\end_layout
\begin_layout Standard
Za povezan multigraf
\begin_inset Formula $G$
\end_inset
eulerjev
\begin_inset Formula $\Leftrightarrow\forall v\in VG:\deg_{G}v$
\end_inset
sod
\end_layout
\begin_layout Standard
Fleuryjev algoritem za eulerjev obhod v eulerjevem grafu: Začnemo v poljubni
povezavi, jo izbrišemo, nadaljujemo na mostu le, če nimamo druge možne
povezave.
\end_layout
\begin_layout Standard
Dekompozicija: delitev na povezavno disjunktne podgrafe.
\end_layout
\begin_layout Standard
Dekompozicija je lepa, če so podgrafi izomorfni.
(
\begin_inset Formula $\exists$
\end_inset
za
\begin_inset Formula $P_{5,2}$
\end_inset
)
\end_layout
\begin_layout Standard
Vsak eulerjev graf premore dekompozicijo v cikle.
\end_layout
\begin_layout Standard
\begin_inset Formula $Q_{n}$
\end_inset
eulerjev
\begin_inset Formula $\Leftrightarrow n$
\end_inset
sod
\end_layout
\begin_layout Standard
\begin_inset Formula $K_{m,n,p}$
\end_inset
eulerjev
\begin_inset Formula $\Leftrightarrow m,n,p$
\end_inset
iste parnosti
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
eulerjev
\begin_inset Formula $\wedge H$
\end_inset
eulerjev
\begin_inset Formula $\Rightarrow G\square H$
\end_inset
eulerjev
\end_layout
\begin_layout Paragraph
Hamiltonov
\end_layout
\begin_layout Standard
cikel vsebuje vsa vozlišča grafa.
\end_layout
\begin_layout Standard
Hamilton graf premore Hamiltonov cikel.
\end_layout
\begin_layout Standard
Hamiltonova pot vsebuje vsa vozlišča.
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
hamiltonov,
\begin_inset Formula $S\subseteq VG\Rightarrow\Omega\left(G-S\right)\leq\left|S\right|$
\end_inset
torej:
\end_layout
\begin_layout Standard
\begin_inset Formula $\exists S\in VG:\Omega\left(G-S\right)>\left|S\right|\Rightarrow G$
\end_inset
ni hamiltonov.
Primer:
\begin_inset Formula $G$
\end_inset
vsebuje prerezno vozlišče
\begin_inset Formula $\Rightarrow G$
\end_inset
ni hamiltonov.
\end_layout
\begin_layout Standard
\begin_inset Formula $K_{n,m}$
\end_inset
je hamiltonov
\begin_inset Formula $\Leftrightarrow m=n$
\end_inset
(za
\begin_inset Formula $S$
\end_inset
vzamemo
\begin_inset Formula $\min\left\{ m,n\right\} $
\end_inset
)
\end_layout
\begin_layout Standard
\begin_inset Formula $\left|VG\right|\geq3,\forall u,v\in VG:\deg_{G}u+\deg_{G}v\geq\left|VG\right|\Rightarrow G$
\end_inset
hamil.
\end_layout
\begin_layout Standard
Dirac:
\begin_inset Formula $\left|VG\right|\geq3,\forall u\in VG:\deg_{G}u\geq\frac{\left|VG\right|}{2}\Rightarrow G$
\end_inset
hamilton.
\end_layout
\begin_layout Paragraph
Ravninski
\end_layout
\begin_layout Standard
graf brez sekanja povezav narišemo v ravnino
\end_layout
\begin_layout Standard
\begin_inset Formula $K_{2,3}$
\end_inset
je ravninski,
\begin_inset Formula $K_{3,3}$
\end_inset
,
\begin_inset Formula $K_{5}$
\end_inset
,
\begin_inset Formula $C_{5}\square C_{5}$
\end_inset
in
\begin_inset Formula $P_{5,2}$
\end_inset
niso ravninski.
\end_layout
\begin_layout Standard
Vložitev je ravninski graf z ustrezno risbo v ravnini.
\end_layout
\begin_layout Standard
Lica so sklenjena območja vložitve brez vozlišč in povezav.
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
lahko vložimo v ravnino
\begin_inset Formula $\Leftrightarrow G$
\end_inset
lahko vložimo na sfero.
\end_layout
\begin_layout Standard
Dolžina lica
\begin_inset Formula $F\sim lF$
\end_inset
je št.
povezav obhoda lica.
\end_layout
\begin_layout Standard
Drevo je ravninski graf z enim licem dolžine
\begin_inset Formula $2\left|ET\right|$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\sum_{F\in FG}lF=2\left|EG\right|$
\end_inset
,
\begin_inset Formula $lF\geq gG$
\end_inset
za ravninski
\begin_inset Formula $G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $2\left|EG\right|=\sum_{F\in FG}lF\geq\sum_{F\in FG}gG=gG\left|FG\right|$
\end_inset
(
\begin_inset Formula $G$
\end_inset
ravn.)
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
ravninski
\begin_inset Formula $\Rightarrow\left|EG\right|\geq\frac{gG}{2}$
\end_inset
\begin_inset Formula $\left|FG\right|$
\end_inset
\end_layout
\begin_layout Standard
Euler:
\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=1+\Omega G$
\end_inset
za ravninski
\begin_inset Formula $G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
ravninski,
\begin_inset Formula $\left|VG\right|\geq3\Rightarrow\left|EG\right|\leq3\left|VG\right|-6$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
ravninski brez
\begin_inset Formula $C_{3}$
\end_inset
,
\begin_inset Formula $\left|VG\right|\geq3\Rightarrow\left|EG\right|\text{\ensuremath{\leq2\left|VG\right|-4}}$
\end_inset
\end_layout
\begin_layout Standard
Triangulacija je taka vložitev, da so vsa lica omejena s
\begin_inset Formula $C_{3}$
\end_inset
.
\end_layout
\begin_layout Standard
V maksimalen ravninski graf ne moremo dodati povezave, da bi ostal ravninski.
\begin_inset Formula $\sim$
\end_inset
Ni pravi vpet podgraf ravn.
grafa.
\end_layout
\begin_layout Standard
\begin_inset Formula $K_{5}-e$
\end_inset
je maksimalen ravninski graf
\begin_inset Formula $\forall e\in EK_{5}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
ravninski.
NTSE:
\begin_inset Formula $G$
\end_inset
triangulacija
\begin_inset Formula $\Leftrightarrow G$
\end_inset
maksimalen ravninski
\begin_inset Formula $\Leftrightarrow\left|EG\right|=3\left|VG\right|-6$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
ravninski
\begin_inset Formula $\Leftrightarrow$
\end_inset
vsaka subdivizija
\begin_inset Formula $G$
\end_inset
ravninska.
\end_layout
\begin_layout Standard
Kuratovski:
\begin_inset Formula $G$
\end_inset
ravn.
\begin_inset Formula $\Leftrightarrow$
\end_inset
ne vsebuje subdivizije
\begin_inset Formula $K_{5}$
\end_inset
ali
\begin_inset Formula $K_{3,3}$
\end_inset
\end_layout
\begin_layout Standard
Wagner:
\begin_inset Formula $G$
\end_inset
ravn.
\begin_inset Formula $\Leftrightarrow$
\end_inset
niti
\begin_inset Formula $K_{5}$
\end_inset
niti
\begin_inset Formula $K_{3,3}$
\end_inset
nista njegova minorja
\end_layout
\begin_layout Standard
Zunanje-ravninski ima vsa vozlišča na robu zunanjega lica.
\end_layout
\begin_layout Standard
\begin_inset Formula $2-$
\end_inset
povezan zunanje-ravninski je
\series bold
hamiltonov
\series default
.
\end_layout
\begin_layout Standard
Zunanje-ravninski
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $\left|VG\right|\geq2$
\end_inset
ima vozlišče stopnje
\begin_inset Formula $\leq2$
\end_inset
.
\end_layout
\begin_layout Paragraph
Barvanje vozlišč
\end_layout
\begin_layout Standard
je taka
\begin_inset Formula $C:VG\to\left\{ 1..k\right\} \Leftrightarrow\forall uv\in EG:Cu\not=Cv$
\end_inset
\end_layout
\begin_layout Standard
Kromatično število
\begin_inset Formula $\chi G$
\end_inset
je najmanjši
\begin_inset Formula $k$
\end_inset
,
\begin_inset Formula $\ni:\exists$
\end_inset
\begin_inset Formula $k-$
\end_inset
barvanje
\begin_inset Formula $G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\chi C_{n}=\begin{cases}
2 & ;n\text{ sod}\\
3 & ;n\text{ lih}
\end{cases}$
\end_inset
,
\begin_inset Formula $\chi G\leq\left|VG\right|,\chi G=\left|VG\right|\Leftrightarrow G\cong K_{n}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
podgraf
\begin_inset Formula $G\Rightarrow\chi G\geq\chi H$
\end_inset
.
\begin_inset Formula $\chi\text{bipartitni}=2$
\end_inset
\end_layout
\begin_layout Standard
Barvni razred so vsa vozlišča iste barve.
Je brez povezav
\begin_inset Formula $\sim$
\end_inset
\series bold
neodvisna množica
\series default
.
\end_layout
\begin_layout Standard
\begin_inset Formula $\chi G=k\Leftrightarrow\chi G\leq k\wedge\chi G\geq k$
\end_inset
\end_layout
\begin_layout Standard
Klično št.:
\begin_inset Formula $\omega G\coloneqq$
\end_inset
\begin_inset Formula $\left|V\right|$
\end_inset
najv.
polnega podgr.
v
\begin_inset Formula $G$
\end_inset
.
\begin_inset Formula $\omega G\leq\chi G$
\end_inset
.
\end_layout
\begin_layout Standard
Trditev:
\begin_inset Formula $\forall n\in\mathbb{N}\exists G\in\mathcal{G}\ni:\omega G=2\wedge\chi G=n$
\end_inset
\end_layout
\begin_layout Standard
Požrešno barvanje: Vozlišča v poljubnem vrstnem redu barvamo z najnižno
možno barvo.
\end_layout
\begin_layout Standard
Vedno
\begin_inset Formula $\exists$
\end_inset
vrstni red, ki vrne barvanje s
\begin_inset Formula $\chi G$
\end_inset
barvami.
\end_layout
\begin_layout Standard
\begin_inset Formula $\forall G\in\mathcal{G}:\chi G\leq\Delta G+1$
\end_inset
, če
\begin_inset Formula $G$
\end_inset
ni regularen celo
\begin_inset Formula $\chi G\leq\Delta G$
\end_inset
\end_layout
\begin_layout Standard
Brooks:
\begin_inset Formula $G$
\end_inset
povezan,
\begin_inset Formula $G$
\end_inset
ni poln niti lihi cikel
\begin_inset Formula $\Rightarrow\chi G\leq\Delta G$
\end_inset
\end_layout
\begin_layout Standard
let
\begin_inset Formula $d_{1}\geq\cdots\geq d_{n}$
\end_inset
stopnje.
\begin_inset Formula $\chi G=1+\max_{i=1}^{n}\min\left\{ d_{i},i-1\right\} $
\end_inset
\end_layout
\begin_layout Standard
Spoj
\begin_inset Formula $G\oplus H$
\end_inset
je disjunktna unija
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $H$
\end_inset
z vsemi pov.
med njima
\end_layout
\begin_layout Standard
Disjunktna unija je unija brez preseka.
\end_layout
\begin_layout Standard
\begin_inset Formula $\chi\left(G\oplus H\right)=\chi G+\chi H$
\end_inset
\end_layout
\begin_layout Standard
Ravninski graf ima
\begin_inset Formula $\chi G\leq4$
\end_inset
\end_layout
\begin_layout Paragraph
Barvanje povezav
\end_layout
\begin_layout Standard
Povezavi s skupnim vozl.
\begin_inset Formula $\Rightarrow$
\end_inset
razl.
barvi.
\end_layout
\begin_layout Standard
Kromatični indeks
\begin_inset Formula $\chi'G$
\end_inset
je najm.
št.
barv za barv.
pov.
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $\chi'C_{n}=\begin{cases}
2 & ;n\text{ sod}\\
3 & ;n\text{ lih}
\end{cases}$
\end_inset
\end_layout
\begin_layout Standard
Vizing:
\begin_inset Formula $\forall G\in\mathcal{G}:\Delta G\geq\chi'G\geq\Delta G+1$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\chi G\in\left\{ \Delta G\text{ razred I.},\Delta G+1\text{ razred II.}\right\} $
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $K_{2k+1}\in$
\end_inset
II.,
\begin_inset Formula $K_{2k}\in$
\end_inset
I., bipartitni
\begin_inset Formula $\in$
\end_inset
I.
\end_layout
\begin_layout Paragraph
Neodvisne množice
\end_layout
\begin_layout Standard
\begin_inset Formula $I\subseteq VG$
\end_inset
je neodvisna, če je podgraf, induciran z
\begin_inset Formula $I$
\end_inset
, brez povezav.
\end_layout
\begin_layout Standard
Neodvisnostno št
\begin_inset Formula $\alpha G$
\end_inset
je moč največje neodvisne množice.
\end_layout
\begin_layout Standard
\begin_inset Formula $\alpha K_{n}=1$
\end_inset
,
\begin_inset Formula $\alpha C_{n}=\lfloor\frac{n}{2}\rfloor$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\alpha G\leq\sum_{i=1}^{k}\alpha H_{i}$
\end_inset
, kjer so
\begin_inset Formula $H_{i}$
\end_inset
disjunktni inducirani podgr.
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $\forall G\in\mathcal{G}:\alpha G\cdot\chi G\geq\left|VG\right|$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\frac{\left|VG\right|}{\chi G}\leq\alpha G\leq\left|VG\right|-\frac{\left|EG\right|}{\Delta G}$
\end_inset
— zgornja in spodnja meja.
\end_layout
\begin_layout Standard
\begin_inset Formula $Iu$
\end_inset
je
\begin_inset Formula $\alpha$
\end_inset
poddrevesa s korenom
\begin_inset Formula $u$
\end_inset
v
\begin_inset Formula $T$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\alpha T=Ir=\max\left\{ 1+\sum_{u\text{ sinovi }r}Iu,\sum_{u\text{ vnuki }r}Iu\right\} $
\end_inset
\end_layout
\begin_layout Paragraph
Dominantne množice
\end_layout
\begin_layout Standard
Neodvisna
\begin_inset Formula $I\subseteq G$
\end_inset
je maksimalna
\begin_inset Formula $\sim\nexists S\text{ neodvisna}\subseteq G\ni:I\subset S\sim$
\end_inset
ni prava
\begin_inset Formula $\subset$
\end_inset
neodv.
mn.
\end_layout
\begin_layout Standard
Dominantna množica je maksimalna neodvisna, kjer ima vsako vozlišče iz
\begin_inset Formula $G\setminus I$
\end_inset
soseda v
\begin_inset Formula $I$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $D\subseteq VG$
\end_inset
dominira
\begin_inset Formula $X\subseteq VG$
\end_inset
, če je vsako vozlišče iz
\begin_inset Formula $X$
\end_inset
v
\begin_inset Formula $D$
\end_inset
ali pa ima soseda v
\begin_inset Formula $D$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $N_{G}\left(u\right)=$
\end_inset
sosedje
\begin_inset Formula $u$
\end_inset
v
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $N_{G}\left[u\right]=N_{G}\left(u\right)\cup\left\{ u\right\} $
\end_inset
zap.
sos.
\begin_inset Formula $u$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $N_{G}\left[D\right]=\bigcup_{u\in D}N_{G}\left[u\right]$
\end_inset
zaprta soseščina množice
\begin_inset Formula $D$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $D$
\end_inset
dominira
\begin_inset Formula $X\sim X\subseteq N_{G}\left[D\right]$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $D$
\end_inset
dominira
\begin_inset Formula $VG\sim D$
\end_inset
dominantna množica
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Standard
Dominacijsko število
\begin_inset Formula $\gamma G=$
\end_inset
moč največje dom.
mn.
\end_layout
\begin_layout Standard
Vsaka maksimalna neodvisna mn.
\begin_inset Formula $G$
\end_inset
je dom.
mn.
\begin_inset Formula $G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\gamma K_{n}=1$
\end_inset
,
\begin_inset Formula $\gamma C_{n}=\lceil\frac{n}{3}\rceil$
\end_inset
,
\begin_inset Formula $\gamma P=3$
\end_inset
\end_layout
\begin_layout Standard
Za vsak graf brez izoliranih vozlišč
\begin_inset Formula $\lceil\frac{\left|VG\right|}{\Delta G+1}\rceil\leq\gamma G\leq\lfloor\frac{\left|VG\right|}{2}\rfloor$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $X$
\end_inset
je 2-pakiranje
\begin_inset Formula $G$
\end_inset
, če
\begin_inset Formula $\forall x,y\in X:x\not=y\Rightarrow d_{G}\left(x,y\right)\geq3$
\end_inset
zdb
\begin_inset Formula $\forall x,y\in X:x\not=y\Rightarrow N_{G}x\cap N_{G}y=\emptyset$
\end_inset
\end_layout
\begin_layout Standard
Moč največjega 2-pakiranja je 2-pakirno število
\begin_inset Formula $\rho G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\Rightarrow\gamma G\geq\rho G$
\end_inset
\end_layout
\begin_layout Standard
Dominantna
\begin_inset Formula $X$
\end_inset
je popolna koda
\begin_inset Formula $G\Leftrightarrow\bigcup_{u\in X}N_{G}\left[u\right]=VG$
\end_inset
\end_layout
\begin_layout Standard
Če graf premore popolno kodo
\begin_inset Formula $\Rightarrow\gamma G=\rho G$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
vpet podgraf
\begin_inset Formula $G\Rightarrow\gamma G\leq\gamma H$
\end_inset
\end_layout
\begin_layout Standard
Povezan
\begin_inset Formula $G$
\end_inset
premore vpeto drevo
\begin_inset Formula $T\ni:\gamma G=\gamma T$
\end_inset
.
Dokaz: odstrani vse povezave, kjer
\begin_inset Formula $G-e$
\end_inset
ohrani
\begin_inset Formula $\gamma$
\end_inset
in povezanost.
\end_layout
\begin_layout Standard
\begin_inset Formula $\left|VG\right|\geq1\Rightarrow\gamma G\leq\chi\overline{G}$
\end_inset
\end_layout
\begin_layout Standard
Povezana dom.
mn.
inducira povez.
podgraf.
—
\begin_inset Formula $\gamma_{c}$
\end_inset
\end_layout
\begin_layout Standard
Neodvisna dom.
mn.
inducira podgraf brez povezav —
\begin_inset Formula $\gamma_{i}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $X$
\end_inset
je celotna dom.
mn.
\begin_inset Formula $\Leftrightarrow\forall v\in VG:N_{G}\left(v\right)\cap X\not=\emptyset$
\end_inset
—
\begin_inset Formula $\gamma_{t}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $G$
\end_inset
brez izol.
vozl.:
\begin_inset Formula $\gamma G\leq\gamma_{t}G\leq2\gamma G$
\end_inset
\end_layout
\begin_layout Paragraph
Algebrske strukture z eno operacijo
\end_layout
\begin_layout Standard
Grupoid: notranjost, polgrupa: asociativen grupoid, monoid: polgrupa z enoto
\end_layout
\begin_layout Standard
Grupa:
\begin_inset Formula $\forall a\in A\exists a^{-1}\in A\ni:a\cdot a^{-1}=a^{-1}\cdot a=e$
\end_inset
\end_layout
\begin_layout Standard
Potence v monoidu:
\begin_inset Formula $n\in\mathbb{N}_{0}$
\end_inset
.
\begin_inset Formula $a^{0}=e$
\end_inset
,
\begin_inset Formula $a^{n}=a\cdot a^{n-1}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(a\cdot b\right)^{-1}=b^{-1}\cdot a^{-1}$
\end_inset
,
\begin_inset Formula $a^{n}\cdot a^{m}=a^{n+m},\left(a^{n}\right)^{m}=a^{nm}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(a^{-1}\right)^{n}=\left(a^{n}\right)^{-1}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(\mathbb{Z}_{m},+_{m}\right)$
\end_inset
grupa,
\begin_inset Formula $\left(\mathbb{Z}_{m},\cdot_{n}\right)$
\end_inset
monoid
\end_layout
\begin_layout Standard
\begin_inset Formula $k\in\mathbb{Z}_{n}$
\end_inset
obrnljiv v
\begin_inset Formula $\left(\mathbb{Z}_{n},\cdot_{n}\right)\Leftrightarrow k\perp n\sim\gcd\left\{ k,n\right\} =1$
\end_inset
\end_layout
\begin_layout Standard
Komutativni grupi pravimo abelova.
\end_layout
\begin_layout Standard
Cayleyeva tabela je predpis za grupoid
\begin_inset Formula $\cdot:A^{2}\to A$
\end_inset
.
\end_layout
\begin_layout Standard
red
\begin_inset Formula $a$
\end_inset
je najmanjši
\begin_inset Formula $n\in\mathbb{N}\ni:a^{n}=e$
\end_inset
oz.
\begin_inset Formula $\infty$
\end_inset
, če ne obstaja.
\end_layout
\begin_layout Standard
Def.:
\begin_inset Formula $H\subseteq G$
\end_inset
podgrupa, če je grupa za isto operacijo.
\end_layout
\begin_layout Standard
Izrek:
\begin_inset Formula $H\subseteq G$
\end_inset
podgrupa
\begin_inset Formula $\Leftrightarrow\forall x,y\in H:x^{-1}y\in H$
\end_inset
\end_layout
\begin_layout Standard
Trivialni podgrupi
\begin_inset Formula $G$
\end_inset
sta
\begin_inset Formula $\left\{ e\right\} $
\end_inset
in
\begin_inset Formula $G$
\end_inset
.
\begin_inset space \hfill{}
\end_inset
Ciklična podgrupa:
\end_layout
\begin_layout Standard
\begin_inset Formula $\left\langle a\right\rangle \coloneqq\left\{ a^{n};\forall n\in\mathbb{Z}\right\} $
\end_inset
je podgrupa v
\begin_inset Formula $G$
\end_inset
za
\begin_inset Formula $a\in\text{grupa }G$
\end_inset
\end_layout
\begin_layout Standard
Center grupe:
\begin_inset Formula $ZG=\left\{ a\in G;\forall x\in G:ax=xa\right\} $
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(ZG,\cdot\right)$
\end_inset
je podgrupa grupe
\begin_inset Formula $\left(G,\cdot\right)$
\end_inset
.
\end_layout
\begin_layout Paragraph
Permutacijske grupe
\end_layout
\begin_layout Standard
Permutacija je bijekcija
\begin_inset Formula $A\to A$
\end_inset
.
\end_layout
\begin_layout Standard
perm.
gr.
so permutacije
\begin_inset Formula $A$
\end_inset
, ki tvorijo grupo za
\begin_inset Formula $\circ$
\end_inset
.
\end_layout
\begin_layout Standard
Polna simetrična grupa
\begin_inset Formula $S_{n}\coloneqq\left\{ \pi:\left\{ 1..n\right\} \to\left\{ 1..n\right\} ;\pi\text{ bijekcija}\right\} $
\end_inset
\end_layout
\begin_layout Standard
Alternirajoča grupa
\begin_inset Formula $A_{n}\coloneqq\left\{ \pi\in S_{n};\pi\text{ soda}\right\} $
\end_inset
\end_layout
\begin_layout Standard
Permutacija kot produkt disjunktnih ciklov dolžin
\begin_inset Formula $l_{1},\dots,l_{n}$
\end_inset
je soda, če je
\begin_inset Formula $\left(l_{1}-1\right)+\cdots+\left(l_{n}-1\right)$
\end_inset
sod.
\end_layout
\begin_layout Standard
\begin_inset Formula $\left|S_{n}\right|=n!$
\end_inset
,
\begin_inset Formula $\left|A_{n}\right|=\frac{n!}{2}$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(G,\circ\right)$
\end_inset
,
\begin_inset Formula $\left(H,*\right)$
\end_inset
grupi.
\begin_inset Formula $f:G\to H$
\end_inset
je hm
\begin_inset Formula $\varphi\Leftrightarrow\forall x,y\in G:f\left(x\circ y\right)=fx*fy$
\end_inset
.
\begin_inset Formula $f$
\end_inset
je še celo im
\begin_inset Formula $\varphi\Leftrightarrow f$
\end_inset
bijekcija.
\end_layout
\begin_layout Standard
Grupi sta izomorfni
\begin_inset Formula $\sim\text{\ensuremath{\exists}}$
\end_inset
im
\begin_inset Formula $\varphi$
\end_inset
med njima:
\begin_inset Formula $G\approx H$
\end_inset
\end_layout
\begin_layout Standard
Vsaka grupa je izomorfna neki permutacijski grupi
\end_layout
\begin_layout Paragraph
Odseki in podgrupe edinke
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(G,\circ\right)$
\end_inset
grupa,
\begin_inset Formula $H\subseteq G$
\end_inset
.
za
\begin_inset Formula $a\in G$
\end_inset
:
\begin_inset Formula $aH=\left\{ ah;h\in H\right\} ,Ha=\left\{ ha;h\in H\right\} $
\end_inset
.
Za
\begin_inset Formula $H$
\end_inset
podgrupo pravimo
\begin_inset Formula $aH$
\end_inset
levi odsek
\begin_inset Formula $H$
\end_inset
in
\begin_inset Formula $Ha$
\end_inset
desni.
Velja:
\begin_inset Formula $a\in aH$
\end_inset
,
\begin_inset Formula $aH=H\Leftrightarrow a\in H$
\end_inset
,
\begin_inset Formula $aH=bH\nabla aH\cap bH=\emptyset$
\end_inset
,
\begin_inset Formula $aH=bH\Leftrightarrow a^{-1}b\in H$
\end_inset
,
\begin_inset Formula $\left|aH\right|=\left|bH\right|$
\end_inset
,
\begin_inset Formula $aH=Ha\Leftrightarrow H=aHa^{-1}$
\end_inset
,
\begin_inset Formula $aH\subseteq G\Leftrightarrow a\in H$
\end_inset
\end_layout
\begin_layout Standard
general linear
\begin_inset Formula $GL_{2}\mathbb{R}=\left\{ A\in M_{2,2}\mathbb{R},\det A\not=0\right\} $
\end_inset
\end_layout
\begin_layout Standard
special linear
\begin_inset Formula $SL_{2}\mathbb{R}=\left\{ A\in M_{2,2}\mathbb{R},\det A=1\right\} $
\end_inset
\end_layout
\begin_layout Standard
Lagrange:
\begin_inset Formula $H$
\end_inset
podgrupa končne grupe
\begin_inset Formula $G\Rightarrow\left|H\right|\text{ deli }\left|G\right|$
\end_inset
in število različnih levih/desnih odeskov po
\begin_inset Formula $H$
\end_inset
je
\begin_inset Formula $\frac{\left|G\right|}{\left|H\right|}$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $a\in$
\end_inset
končne grupe
\begin_inset Formula $G\Rightarrow$
\end_inset
red
\begin_inset Formula $a$
\end_inset
deli
\begin_inset Formula $\left|G\right|$
\end_inset
\end_layout
\begin_layout Paragraph
Podgrupe edinke in faktorske grupe
\end_layout
\begin_layout Standard
\begin_inset Formula $H$
\end_inset
podgrupa
\begin_inset Formula $G$
\end_inset
je edinka
\begin_inset Formula $\Leftrightarrow\forall a\in G:aH=Ha\sim aHa^{-1}=H$
\end_inset
\end_layout
\begin_layout Standard
Podgrupa konjugiranka
\begin_inset Formula $H^{a}\coloneqq aHa^{-1}$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $H\triangleleft G\sim H$
\end_inset
edinka v
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $\Leftrightarrow\forall a\in G:H^{A}=H$
\end_inset
\end_layout
\begin_layout Standard
V Abelovi grupi je vsaka podgrupa edinka.
\end_layout
\begin_layout Standard
Center je podgrupa edinka.
\end_layout
\begin_layout Standard
\begin_inset Formula $G/H\coloneqq\left\{ aH:a\in G\right\} $
\end_inset
z oper.
\begin_inset Formula $\left(aH\right)*\left(bH\right)=\left(ab\right)H$
\end_inset
\end_layout
\begin_layout Standard
Izrek o faktorskih grupah:
\begin_inset Formula $H\triangleleft G\Rightarrow\left(G/H,*\right)$
\end_inset
grupa
\end_layout
\begin_layout Paragraph
Kolobarji in polja
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(R,+,\cdot\right)\text{kolobar}\Rightarrow$
\end_inset
\begin_inset Formula $\left(R,+\right)$
\end_inset
abelova grupa,
\begin_inset Formula $\left(R,\cdot\right)$
\end_inset
polgrupa, distributivnost.
\end_layout
\begin_layout Standard
Kolobar je komutativen, če je
\begin_inset Formula $\cdot$
\end_inset
komutativna.
\end_layout
\begin_layout Standard
Kolobar je z enoto, če obstaja enota za
\begin_inset Formula $\cdot$
\end_inset
.
\end_layout
\begin_layout Standard
Direktna vsota kolobarjev
\begin_inset Formula $\left(R\oplus S,+,\cdot\right)$
\end_inset
je kolobar.
\begin_inset Formula $R\oplus S=R\times S$
\end_inset
,
\begin_inset Formula $+$
\end_inset
in
\begin_inset Formula $\cdot$
\end_inset
po komponentah.
\end_layout
\begin_layout Standard
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
komutativna
\begin_inset Formula $\Rightarrow R\oplus S$
\end_inset
komutativen.
\end_layout
\begin_layout Standard
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
z enoto
\begin_inset Formula $\Rightarrow R\oplus S$
\end_inset
z enoto.
\end_layout
\begin_layout Standard
\begin_inset Formula $R$
\end_inset
kolobar.
\begin_inset Formula $S\subseteq R$
\end_inset
je za podedovani operaciji kolobar, če je
\begin_inset Formula $\left(S,+,\cdot\right)$
\end_inset
kolobar.
Izrek:
\begin_inset Formula $S$
\end_inset
podkolobar
\begin_inset Formula $\Leftrightarrow0\in S$
\end_inset
in zaprta za
\begin_inset Formula $-,\cdot$
\end_inset
\end_layout
\begin_layout Standard
Center kolobarja:
\begin_inset Formula $ZR=\left\{ a\in R;\forall x\in R:ax=xa\right\} $
\end_inset
je podk.
\end_layout
\begin_layout Paragraph
Delitelji niča in celi kolobarji
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(\mathbb{Z}_{n},+_{n},\cdot_{n}\right)$
\end_inset
je vedno kol.
\end_layout
\begin_layout Standard
Def.: Če v kolobarju velja
\begin_inset Formula $ab=0$
\end_inset
in
\begin_inset Formula $a\not=0$
\end_inset
in
\begin_inset Formula $b\not=0$
\end_inset
, sta
\begin_inset Formula $a$
\end_inset
in
\begin_inset Formula $b$
\end_inset
delitelja niča.
\end_layout
\begin_layout Standard
Pravilo krajšanja:
\begin_inset Formula $\forall a,b,c\in R,a\not=0:ab=ac\Rightarrow b=c$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $R$
\end_inset
cel
\begin_inset Formula $\Leftrightarrow$
\end_inset
komutativen z enoto
\begin_inset Formula $1\not=0$
\end_inset
brez deliteljev niča.
\end_layout
\begin_layout Standard
Za komutativen z enoto
\begin_inset Formula $1\not=0$
\end_inset
velja: cel
\begin_inset Formula $\Leftrightarrow$
\end_inset
velja prav.
krajš.
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
z enoto
\begin_inset Formula $1\not=0$
\end_inset
je polje, če je
\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
\end_inset
abelova g.
\end_layout
\begin_layout Standard
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
z enoto
\begin_inset Formula $1\not=0$
\end_inset
je obseg, če je
\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
\end_inset
grupa.
\end_layout
\begin_layout Standard
Vsako polje je cel kolobar.
\end_layout
\begin_layout Standard
Polje je cel kolobar z multiplik.
inverzi za vse neničelne.
\end_layout
\begin_layout Standard
Končen cel kolobar
\begin_inset Formula $\Rightarrow$
\end_inset
polje.
\end_layout
\begin_layout Standard
\begin_inset Formula $\forall n\in\mathbb{N}\setminus\left\{ 1\right\} :\mathbb{Z}_{n}$
\end_inset
cel
\begin_inset Formula $\Leftrightarrow$
\end_inset
\begin_inset Formula $\mathbb{Z}_{n}$
\end_inset
polje
\begin_inset Formula $\Leftrightarrow$
\end_inset
\begin_inset Formula $n$
\end_inset
praštevilo
\end_layout
\begin_layout Standard
\begin_inset Formula $S\subseteq$
\end_inset
polje
\begin_inset Formula $R$
\end_inset
je podpolje za poded.
operaciji, če je
\begin_inset Formula $S$
\end_inset
polje.
Zadošča preveriti
\begin_inset Formula $1\in S$
\end_inset
, zaprtost za
\begin_inset Formula $-$
\end_inset
in deljenje z nenič.ž
\end_layout
\begin_layout Standard
\begin_inset Formula $n\cdot'a$
\end_inset
naj pomeni
\begin_inset Formula $a+\cdots+a$
\end_inset
\begin_inset Formula $n$
\end_inset
-krat za
\begin_inset Formula $n\in\mathbb{N}$
\end_inset
\end_layout
\begin_layout Standard
Karakteristika kolobarja je najmanjši
\begin_inset Formula $n\in N\ni:\forall a\in R:n\cdot'a=0$
\end_inset
.
Če ne obstaja, pravimo char
\begin_inset Formula $R=0$
\end_inset
.
\end_layout
\begin_layout Standard
Izrek: Če je red1
\begin_inset Formula $=n\Rightarrow$
\end_inset
char
\begin_inset Formula $R=n$
\end_inset
\end_layout
\begin_layout Standard
Izrek: Za cel kolobar
\begin_inset Formula $R$
\end_inset
je char
\begin_inset Formula $R=0$
\end_inset
ali char
\begin_inset Formula $R=$
\end_inset
praštevilo
\end_layout
\begin_layout Paragraph
Ideali
\end_layout
\begin_layout Standard
\begin_inset Formula $S$
\end_inset
podkolobar
\begin_inset Formula $R$
\end_inset
je ideal
\begin_inset Formula $R\Leftrightarrow\forall r\in R,s\in S:rs,sr\in S$
\end_inset
\end_layout
\begin_layout Standard
Primer: večkratniki
\begin_inset Formula $n$
\end_inset
so za fiksen
\begin_inset Formula $n$
\end_inset
ideal v
\begin_inset Formula $\mathbb{Z}$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Formula $I\subseteq R$
\end_inset
je ideal
\begin_inset Formula $\Leftrightarrow0\in I$
\end_inset
, zaprt za
\begin_inset Formula $-$
\end_inset
, zaprt za zunanje množ.
\end_layout
\begin_layout Standard
Operaciji nad ideali:
\begin_inset Formula $I\overset{+}{\cdot}J=\left\{ i\overset{+}{\cdot}j;\forall i\in I,j\in J\right\} $
\end_inset
\end_layout
\begin_layout Standard
Za ideala
\begin_inset Formula $I,J$
\end_inset
v
\begin_inset Formula $R$
\end_inset
sta
\begin_inset Formula $I+J$
\end_inset
in
\begin_inset Formula $I\cdot J$
\end_inset
zopet ideala v
\begin_inset Formula $R$
\end_inset
.
\end_layout
\begin_layout Standard
V aditivne odseke
\begin_inset Formula $R/I=\left\{ a+I;\forall a\in R\right\} $
\end_inset
vpeljemo operaciji
\begin_inset Formula $\left(a+I\right)\overset{+}{\cdot}\left(b+I\right)=\left(a\overset{+}{\cdot}b\right)I$
\end_inset
.
Če je
\begin_inset Formula $I$
\end_inset
ideal v
\begin_inset Formula $R$
\end_inset
, je
\begin_inset Formula $R/I$
\end_inset
za operaciji kolobar.
\end_layout
\begin_layout Standard
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
end{multicols}
\end_layout
\end_inset
\end_layout
\end_body
\end_document
