#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