summaryrefslogtreecommitdiffstats
path: root/šola/ds2/kolokvij2.lyx
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--šola/ds2/kolokvij2.lyx3368
1 files changed, 3368 insertions, 0 deletions
diff --git a/šola/ds2/kolokvij2.lyx b/šola/ds2/kolokvij2.lyx
new file mode 100644
index 0000000..0d2e149
--- /dev/null
+++ b/šola/ds2/kolokvij2.lyx
@@ -0,0 +1,3368 @@
+#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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-19 23:47:48 +0100