#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{hyperref}
\usepackage{siunitx}
\usepackage{pgfplots}
\usepackage{listings}
\usepackage{multicol}
\sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}}
\usepackage{amsmath}
\usepackage{tikz}
\newcommand{\udensdash}[1]{%
\tikz[baseline=(todotted.base)]{
\node[inner sep=1pt,outer sep=0pt] (todotted) {#1};
\draw[densely dashed] (todotted.south west) -- (todotted.south east);
}%
}%
\DeclareMathOperator{\Lin}{Lin}
\DeclareMathOperator{\rang}{rang}
\DeclareMathOperator{\sled}{sled}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\red}{red}
\DeclareMathOperator{\karakteristika}{char}
\usepackage{algorithm,algpseudocode}
\providecommand{\corollaryname}{Posledica}
\end_preamble
\use_default_options true
\begin_modules
enumitem
theorems-ams
\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 default
\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 2cm
\topmargin 2cm
\rightmargin 2cm
\bottommargin 2cm
\headheight 2cm
\headsep 2cm
\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 Title
Odgovori na vprašanja za teoretični del izpita DS2 IŠRM 2023/24
\end_layout
\begin_layout Author
\noun on
Anton Luka Šijanec
\end_layout
\begin_layout Date
\begin_inset ERT
status open
\begin_layout Plain Layout
\backslash
today
\end_layout
\end_inset
\end_layout
\begin_layout Abstract
Vprašanja je zbral profesor Sandi Klavžar.
Odgovore sem sestavil po svojih zapiskih z njegovih predavanj in drugih
virih.
\end_layout
\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents
\end_inset
\end_layout
\begin_layout Section
Slog
\end_layout
\begin_layout Itemize
Z
\begin_inset Formula $M_{m,n}\mathbb{F}$
\end_inset
označim množico matrik z
\begin_inset Formula $m$
\end_inset
vrsticami in
\begin_inset Formula $n$
\end_inset
stolpci nad poljem
\begin_inset Formula $\mathbb{F}$
\end_inset
.
\end_layout
\begin_layout Itemize
Znak za množenje ali dvojiški operator v grupi izpuščam.
V bigrupoidih izpuščen operator pomeni množenje (drugo operacijo).
\end_layout
\begin_layout Section
Vprašanja in odgovori
\end_layout
\begin_layout Subsection
Kaj je stopnja vozlišča grafa in kaj pravi lema o rokovanju? Kako dokažemo
to lemo?
\end_layout
\begin_layout Standard
Naj bo
\begin_inset Formula $G$
\end_inset
graf.
\end_layout
\begin_layout Definition*
Stopnja vozlišča grafa
\begin_inset Formula $\deg v$
\end_inset
za
\begin_inset Formula $v\in VG$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
Ko eniški operator zahteva en operand, izpustim oklepaje.
Primer:
\begin_inset Formula $\sin x$
\end_inset
,
\begin_inset Formula $VG$
\end_inset
,
\begin_inset Formula $\chi G$
\end_inset
,
\begin_inset Formula $M_{2,2}\mathbb{R}$
\end_inset
.
\end_layout
\end_inset
predstavlja število povezav, ki imajo to vozlišče kot krajišče.
\begin_inset Formula $\deg v=\left|\left\{ e\in EG;v\in e\right\} \right|$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
Povezava v grafu je množica natanko dveh vozlišč, toda oklepaje in vejico
izpuščam.
Za
\begin_inset Formula $u,v\in VG$
\end_inset
pišem
\begin_inset Formula $uv\in EG$
\end_inset
.
Na
\begin_inset Formula $e\in EG$
\end_inset
je torej veljavno gledati kot na množico, zato je
\begin_inset Formula $v\in e$
\end_inset
smiseln izraz.
\end_layout
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
Zapis množic:
\begin_inset Formula $\left\{ e\in A;Pe\right\} $
\end_inset
pomeni vse take elemente
\begin_inset Formula $A$
\end_inset
, za katere velja predikat
\begin_inset Formula $P$
\end_inset
.
Ta predikat je običajno izraz.
\end_layout
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Incidenčna matrika
\begin_inset Formula $BG$
\end_inset
za
\begin_inset Formula $VG=\left\{ v_{1},\dots,v_{n}\right\} $
\end_inset
,
\begin_inset Formula $EG=\left\{ e_{1},\dots,e_{n}\right\} $
\end_inset
je široka
\begin_inset Formula $m$
\end_inset
in visoka
\begin_inset Formula $n$
\end_inset
in velja
\begin_inset Formula $BG_{ij}=\begin{cases}
1 & ;v_{i}\in e_{i}\\
0 & ;\text{sicer}
\end{cases}$
\end_inset
.
\end_layout
\begin_layout Lemma*
Lema o rokovanju pravi, da je dvakratnik števila povezav enak vsoti vseh
stopenj vozlišč v grafu
\begin_inset Foot
status open
\begin_layout Plain Layout
Ko je omenjen graf, je običajno mišljen neusmerjen končen graf.
\end_layout
\end_inset
, torej
\begin_inset Formula
\[
\sum_{v\in VG}\deg v=2\left|EG\right|.
\]
\end_inset
\end_layout
\begin_layout Remark*
Posledica leme o rokovanju je, da je v vsakem grafu sodo vozlišč lihe stopnje,
saj je vsota soda.
\end_layout
\begin_layout Proof
Če po vozliščih preštevamo povezave, ki se stikajo vozlišča, bi vsako povezavo
šteli dvakrat; vsakič za eno njeno krajišče.
ZDB V vsakem stolpcu incidenčne matrike sta natanko dve enici.
Torej je enic
\begin_inset Formula $2\left|EG\right|$
\end_inset
.
V vsaki vrstici incidenčne matrike je toliko enic, kolikor je stopnja
\begin_inset Formula $i-$
\end_inset
tega vozlišča, torej je enic
\begin_inset Formula $\sum_{v\in VG}\deg v$
\end_inset
.
\end_layout
\begin_layout Subsection
Pojasnite sprehod, sklenjen sprehod, pot v grafu, cikel v grafu.
Pokažite, da vsak graf, ki vsebuje sklenjen sprehod lihe dolžine, vsebuje
tudi cikel lihe dolžine.
\end_layout
\begin_layout Standard
Naj bo
\begin_inset Formula $G=\left(VG,EG\right)$
\end_inset
.
\end_layout
\begin_layout Definition*
Sprehod v
\begin_inset Formula $G$
\end_inset
je zaporedje vozlišč
\begin_inset Formula $v_{0},\dots,v_{k}$
\end_inset
,
\begin_inset Formula $k\geq0$
\end_inset
, tako da je
\begin_inset Formula $\forall i\in\left\{ 1..k\right\} :v_{i}v_{i+1}\in EG$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
S
\begin_inset Formula $\left\{ k..n\right\} $
\end_inset
označujem množico celih števil od vključno
\begin_inset Formula $k$
\end_inset
do vključno
\begin_inset Formula $n$
\end_inset
, kot to naredi
\family typewriter
bash.
\family default
Nekateri bi
\begin_inset Formula $\left\{ 1..n\right\} $
\end_inset
označili z
\begin_inset Formula $\left[n\right]$
\end_inset
.
\end_layout
\end_inset
.
Dolžina sprehoda je število prehojenih povezav.
Sprehod je
\series bold
sklenjen
\series default
, če
\begin_inset Formula $v_{0}=v_{k}$
\end_inset
.
Sprehod je
\series bold
enostaven
\series default
, če so vsa vozlišča medsebojno različna, z izjemo
\begin_inset Formula $v_{0}$
\end_inset
sme biti
\begin_inset Formula $v_{k}$
\end_inset
.
\end_layout
\begin_layout Claim*
Če v grafu
\begin_inset Formula $\exists$
\end_inset
sprehod med dvema vozliščema, med njima obstaja tudi enostaven sprehod.
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $Q$
\end_inset
sprehod med
\begin_inset Formula $u$
\end_inset
in
\begin_inset Formula $v$
\end_inset
.
Če je enostaven, je najden, sicer se ponovita vsaj dve vozlišči in je
\begin_inset Formula $Q$
\end_inset
oblike
\begin_inset Formula $u,\dots,x,\dots,x,\dots,v$
\end_inset
.
Sprehodu priredimo
\begin_inset Formula $Q'$
\end_inset
, ki odstrani pot od prvega do zadnjega podvojenega vozlišča
\begin_inset Formula $x$
\end_inset
, torej je
\begin_inset Formula $Q'$
\end_inset
oblike
\begin_inset Formula $u,\dots,x,\dots,v$
\end_inset
(pravzaprav smo odstranili cikel iz poti).
Če je
\begin_inset Formula $Q'$
\end_inset
enostaven, je iskani, sicer postopek ponovimo in v končno korakih se postopek
ustavi, saj na vsakem koraku za vsaj 2 zmanjšamo dolžino sicer končno dolgega
sprehoda.
\end_layout
\begin_layout Definition*
Pot v grafu je podgraf, ki je enostaven sprehod med dvema vozliščema in
je graf Pot (
\begin_inset Formula $P_{n}$
\end_inset
).
\end_layout
\begin_layout Remark*
Ko govorimo o različnosti/enakosti poti, mislimo različnost/enakost poti
kot podgraf.
Poti sta torej enaki natanko tedaj, ko sta zaporedji (ne množici) vozlišč
poti enaki.
\end_layout
\begin_layout Definition*
Cikel v grafu je podgraf, ki je enostaven sklenjen sprehod dolžine vsaj
3.
\end_layout
\begin_layout Claim*
Če med dvema vozliščema v grafu
\begin_inset Formula $\exists$
\end_inset
dve različni poti, potem graf premore cikel.
\end_layout
\begin_layout Proof
Naj bosta
\begin_inset Formula $P$
\end_inset
in
\begin_inset Formula $P'$
\end_inset
dve različni poti od
\begin_inset Formula $u$
\end_inset
do
\begin_inset Formula $v$
\end_inset
.
Naj bo
\begin_inset Formula $x$
\end_inset
zadnje (če gledamo usmerjeno
\begin_inset Formula $u,v-$
\end_inset
pot) vozlišče, ki je skupno
\begin_inset Formula $P$
\end_inset
in
\begin_inset Formula $P'$
\end_inset
.
\begin_inset Formula $x$
\end_inset
je lahko
\begin_inset Formula $u$
\end_inset
.
Naj bo
\begin_inset Formula $g$
\end_inset
prvo naslednje vozlišče za
\begin_inset Formula $x$
\end_inset
, ki je na
\begin_inset Formula $P$
\end_inset
in
\begin_inset Formula $P'$
\end_inset
.
Unija podpoti
\begin_inset Formula $P$
\end_inset
od
\begin_inset Formula $x$
\end_inset
do
\begin_inset Formula $y$
\end_inset
in podpoti
\begin_inset Formula $P'$
\end_inset
od
\begin_inset Formula $x$
\end_inset
do
\begin_inset Formula $y$
\end_inset
določa iskani cikel v grafu.
\end_layout
\begin_layout Claim*
Če graf premore sklenjen sprehod lihe dolžine, potem premore cikel lihe
dolžine.
\end_layout
\begin_layout Proof
Indukcija po dolžini sprehoda.
Naj bo
\begin_inset Formula $m$
\end_inset
dolžina sprehoda.
\end_layout
\begin_layout Proof
Baza:
\begin_inset Formula $m=3$
\end_inset
, najmanjši sklenjen lihi sprehod je cikel dolžine 3,
\begin_inset Formula $m=4$
\end_inset
, drugi najmanjši sklenjen lihi sprehod je cikel dolžine 4.
\end_layout
\begin_layout Proof
Korak: Naj bo
\begin_inset Formula $Q$
\end_inset
poljuben sklenjen sprehod dolžine
\begin_inset Formula $m\geq5$
\end_inset
.
Če je
\begin_inset Formula $Q$
\end_inset
enostaven, je cikel po definiciji, sicer se vsaj eno vozlišče na sprehodu
vsaj ponovi:
\begin_inset Formula $u,x_{1},\dots,x_{i-1},x_{i},x_{i+1},\dots,x_{j-1},x_{j},x_{j+1},\dots,v$
\end_inset
in velja
\begin_inset Formula $x_{i}=x_{j}$
\end_inset
.
Poglejmo sprehoda
\begin_inset Formula $Q'=x_{i},\dots,x_{j}=x_{i}$
\end_inset
in
\begin_inset Formula $Q''=u,x_{1},\dots,x_{i},x_{j+1},\dots,x_{m}=u$
\end_inset
.
\begin_inset Formula $Q'$
\end_inset
in
\begin_inset Formula $Q''$
\end_inset
sta sklenjena sprehoda z dolžinama
\begin_inset Formula $m'$
\end_inset
in
\begin_inset Formula $m''$
\end_inset
in velja
\begin_inset Formula $m=m'+m''$
\end_inset
.
Ker je
\begin_inset Formula $m$
\end_inset
lih, mora biti lih natanko en izmed
\begin_inset Formula $m'$
\end_inset
in
\begin_inset Formula $m''$
\end_inset
.
BSŠ
\begin_inset Foot
status open
\begin_layout Plain Layout
Brez Škode za Splošnost trdimo, da
\end_layout
\end_inset
\begin_inset Formula $m'$
\end_inset
lih in
\begin_inset Formula $m'<m$
\end_inset
, zato po I.
P.
\begin_inset Formula $m'$
\end_inset
vsebuje lih cikel.
\end_layout
\begin_layout Subsection
Kaj so dvodelni grafi? Kako jih karakteriziramo? Kako dokažemo to karakterizacij
o?
\end_layout
\begin_layout Definition*
\begin_inset Formula $G$
\end_inset
dvodelen
\begin_inset Foot
status open
\begin_layout Plain Layout
Pomožni glagol biti med osebkom in povedkovnikom izpuščam.
\begin_inset Quotes gld
\end_inset
\begin_inset Formula $G$
\end_inset
dvodelen
\begin_inset Quotes grd
\end_inset
namesto
\begin_inset Quotes gld
\end_inset
\begin_inset Formula $G$
\end_inset
je dvodelen
\begin_inset Quotes grd
\end_inset
.
\end_layout
\end_inset
\begin_inset Formula $\Leftrightarrow\exists A,B\subseteq VG\ni:A\cup B=VG,A\cap B=\emptyset\ni:\forall uv\in EG:u\in A,v\in B\vee v\in A,u\in B$
\end_inset
.
ZDB
\begin_inset Foot
status open
\begin_layout Plain Layout
Z Drugimi Besedami:
\end_layout
\end_inset
obstaja razdelitev vozlišč na dve množici, da induciran podgraf posamezne
množice ne vsebuje povezav.
S
\begin_inset Formula $K_{m,n}$
\end_inset
označimo poln dvodelni graf
\begin_inset Formula $\left|A\right|=m$
\end_inset
,
\begin_inset Formula $\left|B\right|=n$
\end_inset
.
Paru
\begin_inset Formula $\left(A,B\right)$
\end_inset
pravimo dvodelna razdelitev.
\end_layout
\begin_layout Theorem*
\begin_inset Formula $G$
\end_inset
dvodelen
\begin_inset Formula $\Leftrightarrow$
\end_inset
\begin_inset Formula $G$
\end_inset
ne vsebuje lihih ciklov.
\end_layout
\begin_layout Proof
\begin_inset Formula $G$
\end_inset
dvodelen
\begin_inset Formula $\Leftrightarrow$
\end_inset
vsaka komponenta
\begin_inset Formula $G$
\end_inset
dvodelna, zato BSŠ
\begin_inset Formula $G$
\end_inset
povezan.
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
Očitno: Če
\begin_inset Formula $G$
\end_inset
vsebuje lih cikel, zagotovo ni dvodelen, saj ne moremo razdeliti niti množice
vozlišč cikla.
S skico dokažemo, da sodi cikli so dvodelni, lihi pa niso (narišemo cikel
kot pot v obliki skeletne formule nenasičenega acikličnega alkana in povežemo
prvo in zadnje vozlišče).
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
\begin_inset Formula $G$
\end_inset
je po predpostavki brez lihih ciklov ****.
Izberimo poljubno
\begin_inset Formula $x_{0}\in VG$
\end_inset
.
Naj bo
\begin_inset Formula $A=\left\{ u\in VG;d_{G}\left(u,x_{0}\right)\text{ sod}\right\} ,B=\left\{ u\in VG;d_{G}\left(u,x_{0}\right)\text{ lih}\right\} $
\end_inset
.
\begin_inset Formula $x_{0}$
\end_inset
je torej v
\begin_inset Formula $A$
\end_inset
, saj je
\begin_inset Formula $d_{G}\left(x_{0},x_{0}\right)=0$
\end_inset
.
Trdimo, da je
\begin_inset Formula $\left(A,B\right)$
\end_inset
dvodelna razdelitev
\begin_inset Formula $G$
\end_inset
.
Razdelitev je, ker je
\begin_inset Formula $A\cup B=\emptyset$
\end_inset
in
\begin_inset Formula $A\cup B=VG$
\end_inset
.
Za dvodelnost pa mora veljati
\begin_inset Formula $\forall X\in\left\{ A,B\right\} :\forall u,v\in X:uv\not\in EG$
\end_inset
.
Preverimo za splošen fiksen
\begin_inset Formula $X\in\left\{ A,B\right\} $
\end_inset
: Naj bosta
\begin_inset Formula $u,v\in X$
\end_inset
, BSŠ
\begin_inset Formula $d_{G}\left(x_{0},u\right)>d_{G}\left(x_{0},v\right)$
\end_inset
*.
Ločimo dva primera:
\end_layout
\begin_deeper
\begin_layout Description
\begin_inset Formula $d_{G}\left(x_{0},u\right)\not=d_{G}\left(x_{0},v\right):$
\end_inset
Vsled iste parnosti velja
\begin_inset Formula $\left|d_{G}\left(x_{0},u\right)-d_{G}\left(x_{0},v\right)\right|\geq2$
\end_inset
***.
PDDRAA
\begin_inset Foot
status open
\begin_layout Plain Layout
Pa Denimo Da sledeča trditev ne drži (Reductio Ad Absurdum)
\end_layout
\end_inset
\begin_inset Formula $uv\in EG$
\end_inset
, tedaj se
\begin_inset Formula $d_{G}\left(x_{0},u\right)$
\end_inset
in
\begin_inset Formula $d_{G}\left(x_{0},v\right)$
\end_inset
razlikujeta za največ 1 in velja
\begin_inset Formula $d_{G}\left(x_{0},u\right)\leq d_{G}\left(x_{0},v\right)+1$
\end_inset
**.
Iz * in ** sledi
\begin_inset Formula $d_{G}\left(x_{0},u\right)-d_{G}\left(x_{0},v\right)=1$
\end_inset
, kar je v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
s trditvijo ***.
\end_layout
\begin_layout Description
\begin_inset Formula $d_{G}\left(x_{0},u\right)=d_{G}\left(x_{0},v\right):$
\end_inset
Naj bo
\begin_inset Formula $P_{x}$
\end_inset
najkrajša
\begin_inset Formula $x_{0},x-$
\end_inset
pot.
PDDRAA
\begin_inset Formula $uv\in EG$
\end_inset
, tedaj
\begin_inset Formula $P_{u}=\left\{ ...P_{v},v\right\} $
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
Prefiksni razširitveni operator
\begin_inset Formula $...$
\end_inset
razširi množico oziroma v tem primeru zaporedje v seznam elementov.
S tem lahko množico uporabimo kot seznam.
Povzemam operator
\family typewriter
...
\family default
iz javascripta.
\end_layout
\end_inset
, torej
\begin_inset Formula $\left|P_{u}\right|=1+\left|P_{v}\right|$
\end_inset
.
Cikel, ki ga tvorijo
\begin_inset Formula $P_{u}$
\end_inset
,
\begin_inset Formula $P_{v}$
\end_inset
in povezava
\begin_inset Formula $uv$
\end_inset
, je torej dolžine
\begin_inset Formula $2\left|P_{v}\right|+1$
\end_inset
, kar je liho število, kar je v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
s trditvijo ****.
\end_layout
\end_deeper
\begin_layout Subsection
Kaj je homomorfizem grafov, izomorfizem grafov in avtomorfizem grafa? Kaj
je to
\begin_inset Formula $\Aut\left(G\right)$
\end_inset
? Kakšno algebrsko strukturo ima?
\end_layout
\begin_layout Standard
Naj bosta
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
grafa.
\end_layout
\begin_layout Definition*
Preslikava
\begin_inset Formula $f:VG\to VH$
\end_inset
je hm
\begin_inset Formula $\varphi$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
homomorfizem
\end_layout
\end_inset
grafov
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H\Leftrightarrow\forall u,v\in VG:uv\in EG\Rightarrow fufv\in EH$
\end_inset
, ZDB če slika povezave v povezave.
\end_layout
\begin_layout Remark*
Če je
\begin_inset Formula $f$
\end_inset
hm
\begin_inset Formula $\text{\ensuremath{\varphi}},$
\end_inset
porodi preslikavo
\begin_inset Formula $f':EG\to EH$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $f:VK_{n,m}\to VK_{2}$
\end_inset
s predpisom
\begin_inset Formula $fx=\begin{cases}
u & ;x\in A\\
v & ;x\in B
\end{cases}$
\end_inset
je hm
\begin_inset Formula $\varphi$
\end_inset
.
\begin_inset Formula $K_{2}$
\end_inset
je homomorfna slika vsakega dvodelnega grafa.
\end_layout
\begin_layout Definition*
Če je hm
\begin_inset Formula $\varphi$
\end_inset
surjektiven po povezavah in vozliščih, je epimorfizem.
Če je injektiven na vozliščih (in posledično na povezavah), je monomorfizem
ali vložitev.
Vložitev je izometrična, če
\begin_inset Formula $\forall u,v\in VG:d_{G}\left(u,v\right)=d_{H}\left(fu,fv\right)$
\end_inset
ZDB ohranja razdalje.
\end_layout
\begin_layout Claim*
Če sta
\begin_inset Formula $f:VG\to VH$
\end_inset
in
\begin_inset Formula $g:VH\to VK$
\end_inset
hm
\begin_inset Formula $\varphi$
\end_inset
, je
\begin_inset Formula $g\circ f:VG\to VK$
\end_inset
spet hm
\begin_inset Formula $\varphi$
\end_inset
.
\end_layout
\begin_layout Definition*
Če je
\begin_inset Formula $f:VG\to VH$
\end_inset
bijekcija, hm
\begin_inset Formula $\varphi$
\end_inset
in
\begin_inset Formula $f^{-1}$
\end_inset
hm
\begin_inset Formula $\varphi$
\end_inset
(ZDB slika nepovezave v nepovezave), je
\begin_inset Formula $f$
\end_inset
im
\begin_inset Formula $\varphi$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
izomorfizem
\end_layout
\end_inset
grafov
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
.
ZDB
\begin_inset Formula $f:VG\to VH$
\end_inset
im
\begin_inset Formula $\varphi$
\end_inset
\begin_inset Formula $\Leftrightarrow f$
\end_inset
bijekcija
\begin_inset Formula $\wedge\forall u,v\in VG:uv\in EG\Leftrightarrow fufv\in EH$
\end_inset
.
Če
\begin_inset Formula $\text{\ensuremath{\exists}}$
\end_inset
im
\begin_inset Formula $\varphi$
\end_inset
grafov
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
, pravimo, da sta
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
izomorfna in pišemo
\begin_inset Formula $G\cong H$
\end_inset
.
\end_layout
\begin_layout Claim*
\begin_inset Formula $\cong$
\end_inset
je na
\begin_inset Formula $\mathcal{G}$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
množica vseh grafov
\end_layout
\end_inset
ekvivalenčna (refleksivna, simetrična, tranzitivna).
\end_layout
\begin_layout Definition*
im
\begin_inset Formula $\varphi$
\end_inset
\begin_inset Formula $G\to G$
\end_inset
je am
\begin_inset Formula $\varphi$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
avtomorfizem
\end_layout
\end_inset
.
Vse am
\begin_inset Formula $\varphi$
\end_inset
grafa
\begin_inset Formula $G$
\end_inset
združimo v množico in jo opremimo z operacijo komponiranja.
Dobimo
\begin_inset Quotes gld
\end_inset
grupo avtomorfizmov grafa
\begin_inset Formula $G$
\end_inset
\begin_inset Quotes grd
\end_inset
, ki jo označimo z
\begin_inset Formula $\Aut G$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $\Aut C_{4}=\left(\left\{ id,\left(2,4\right),\left(12\right)\left(34\right),\left(1234\right),\left(13\right),\left(13\right)\left(24\right),\left(1423\right),\left(4321\right)\right\} ,\circ\right)$
\end_inset
,
\begin_inset Formula $\Aut K_{n}=\left(S_{n},\circ\right)$
\end_inset
za
\begin_inset Formula $S_{n}$
\end_inset
množica vseh permutacij
\begin_inset Formula $n$
\end_inset
elementov,
\begin_inset Formula $\Aut P_{n}=\left(\left\{ id,f\left(i\right)=n-i-1\right\} ,\circ\right)$
\end_inset
\end_layout
\begin_layout Fact*
Za vsako končno grupo
\begin_inset Formula $X$
\end_inset
\begin_inset Formula $\exists$
\end_inset
graf
\begin_inset Formula $G\ni:\Aut G=X$
\end_inset
.
Algebra
\begin_inset Formula $\subseteq$
\end_inset
Diskretne strukture.
Dokaz na magisteriju.
\end_layout
\begin_layout Subsection
Kaj pomeni, da je graf
\begin_inset Formula $H$
\end_inset
minor grafa
\begin_inset Formula $G$
\end_inset
? Kdaj sta dva grafa homeomorfna? Pojasni operacijo kartezičnega produkta
grafov.
\end_layout
\begin_layout Definition*
\series bold
Odstranjevanje vozlišč
\series default
: za neko
\begin_inset Formula $S\subseteq VG$
\end_inset
je
\begin_inset Formula $G-S$
\end_inset
graf, ki ga dobimo, ko iz
\begin_inset Formula $G$
\end_inset
odstranimo vozlišča in vozliščem pripadajoče povezave iz
\begin_inset Formula $S$
\end_inset
.
Za
\begin_inset Formula $S=\left\{ u\right\} $
\end_inset
pišemo tudi
\begin_inset Formula $G-u$
\end_inset
.
\series bold
Odstranjevanje povezav
\series default
: za neko
\begin_inset Formula $F\subseteq EG$
\end_inset
je
\begin_inset Formula $G-F$
\end_inset
graf, ki ga dobimo, ko iz
\begin_inset Formula $G$
\end_inset
odstranimo povezave iz
\begin_inset Formula $F$
\end_inset
.
Za
\begin_inset Formula $S=\left\{ e\right\} $
\end_inset
pišemo tudi
\begin_inset Formula $G-e$
\end_inset
.
\series bold
Skrčitev povezave
\series default
: za
\begin_inset Formula $e=\left\{ u,v\right\} \in EG$
\end_inset
je
\begin_inset Formula $G/e$
\end_inset
graf, ki ga dobimo tako, da identificiramo
\begin_inset Formula $u$
\end_inset
in
\begin_inset Formula $v$
\end_inset
in odstranimo morebitne vzporedne povezave, s čimer odstranimo tudi zanko
\begin_inset Formula $\left\{ u,u=v\right\} $
\end_inset
.
\begin_inset Formula $G/e_{1}/e_{2}/\dots/e_{n}$
\end_inset
označimo z
\begin_inset Formula $G/\left\{ e_{1},e_{2},\dots,e_{n}\right\} $
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
\begin_inset Formula $H$
\end_inset
minor
\begin_inset Formula $G\Leftrightarrow$
\end_inset
\begin_inset Formula $H$
\end_inset
dobimo iz
\begin_inset Formula $G$
\end_inset
z nekim zaporedjem operacij, kjer so dovoljene operacije odstranjevanje
vozlišča, odstranjevanje povezave in skrčitev povezave.
Ekvivalentno je
\begin_inset Formula $H$
\end_inset
minor
\begin_inset Formula $G$
\end_inset
, če ga lahko dobimo iz nekega podgrafa
\begin_inset Formula $G$
\end_inset
, ki mu skrčimo poljubno povezav.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Subdivizija povezav:
\begin_inset Formula $G\to G^{+}e$
\end_inset
za
\begin_inset Formula $e\in EG$
\end_inset
:
\begin_inset Formula $VG^{+}e=VG\cup\left\{ x_{e}\right\} $
\end_inset
,
\begin_inset Formula $EG^{+}e=EG\setminus e\cup\left\{ x_{e}u,x_{e}v\right\} $
\end_inset
.
Graf
\begin_inset Formula $H$
\end_inset
je subdivizija
\begin_inset Formula $G\Leftrightarrow H$
\end_inset
dobimo iz
\begin_inset Formula $G$
\end_inset
z zaporedjem subdivizij povezav
\begin_inset Formula $G$
\end_inset
ZDB povezave v
\begin_inset Formula $G$
\end_inset
zamenjamo s poljubno dolčimi potmi.
Relacija je refleksivna (
\begin_inset Formula $G$
\end_inset
subdivizija
\begin_inset Formula $G$
\end_inset
).
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Glajenje vozlišča
\begin_inset Formula $u$
\end_inset
stopnje
\begin_inset Formula $2$
\end_inset
: (obratna operacija od subdivizije)
\begin_inset Formula $G^{-}u=\left(VG\setminus u,\left(EG\setminus\left\{ e,f\right\} \right)\cup\left\{ \left\{ v,w\right\} \right\} \right)$
\end_inset
, kjer sta
\begin_inset Formula $e$
\end_inset
in
\begin_inset Formula $f$
\end_inset
povezavi, ki vsebujeta
\begin_inset Formula $u$
\end_inset
,
\begin_inset Formula $v$
\end_inset
in
\begin_inset Formula $w$
\end_inset
pa njuni drugi krajišči (tisti krajišči, ki nista
\begin_inset Formula $u$
\end_inset
).
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Grafa sta homeomorfna, če sta izomorfna po gladitvi vseh vozlišč stopnje
2.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Naj bosta
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $H$
\end_inset
grafa.
Kartezični produkt grafov
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
označimo z
\begin_inset Formula $G\square H$
\end_inset
:
\begin_inset Formula $V\left(G\square H\right)=VG\times VH,E\left(G\square H\right)=\left\{ \left(g,h\right)\left(g',h'\right);g=g'\wedge hh'\in EH\vee h=h'\wedge gg'\in EG\right\} $
\end_inset
.
\end_layout
\begin_layout Remark*
\begin_inset Formula $\left(\mathcal{G},\square\right)$
\end_inset
je monoid, kajti
\begin_inset Formula $K_{1}$
\end_inset
je enota, operacija je komutativna in notranja.
\end_layout
\begin_layout Example*
\begin_inset Formula $K_{2}\square K_{2}\cong C_{4}$
\end_inset
\end_layout
\begin_layout Subsection
Kaj so to prerezna vozlišča in prerezne povezave grafa? Kdaj je graf
\begin_inset Formula $k-$
\end_inset
povezan in kaj je to povezanost grafa?
\end_layout
\begin_layout Standard
Naj bo
\begin_inset Formula $G$
\end_inset
graf z
\begin_inset Formula $m$
\end_inset
vozlišči.
\end_layout
\begin_layout Definition*
\begin_inset Formula $u,v\in VG$
\end_inset
sta v isti povezani komponenti, če v
\begin_inset Formula $G$
\end_inset
obstaja sprehod med njima.
Število komponent
\begin_inset Formula $G$
\end_inset
označimo z
\begin_inset Formula $\Omega G$
\end_inset
.
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow\Omega G=1$
\end_inset
.
\end_layout
\begin_layout Remark*
Biti v isti komponenti je ekvivalenčna relacija (refleksivna, simetrična
in tranzitivna).
\end_layout
\begin_layout Definition*
\begin_inset Formula $x\in VG$
\end_inset
prerezno
\begin_inset Formula $\Leftrightarrow\Omega\left(G-x\right)>\Omega G$
\end_inset
.
\begin_inset Formula $e\in EG$
\end_inset
prerezna
\begin_inset Formula $\sim e$
\end_inset
most
\begin_inset Formula $\Leftrightarrow\Omega\left(G-e\right)>\Omega G$
\end_inset
.
\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
.
\begin_inset Formula $X\subseteq EG$
\end_inset
je prerezna množica povezav
\begin_inset Formula $\Leftrightarrow\Omega\left(G-X\right)>\Omega G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Povezan graf
\begin_inset Formula $G$
\end_inset
je
\begin_inset Formula $k-$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow\left|VG\right|\geq k+1\wedge\forall X\text{ prerezna}\subseteq VG:\left|X\right|>=k$
\end_inset
prerezna.
ZDB ima vsaj
\begin_inset Formula $k+1$
\end_inset
vozlišč in
\series bold
ne
\series default
vsebuje prerezne množice moči manjše od
\begin_inset Formula $k$
\end_inset
.
Povezanost grafa
\begin_inset Formula $G\sim\kappa G$
\end_inset
je največji
\begin_inset Formula $k\in\mathbb{N}$
\end_inset
, za katerega je
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $k-$
\end_inset
povezan ZDB najmanjše število vozlišč, ki jih moramo odstraniti iz grafa,
da graf ne bo več povezan.
\end_layout
\begin_layout Remark*
\begin_inset Formula $\kappa G=k\Rightarrow G$
\end_inset
nima prerezne množice moči
\begin_inset Formula $<k$
\end_inset
.
\end_layout
\begin_layout Example*
\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_{m,n}=\min\left\{ n,m\right\} $
\end_inset
,
\begin_inset Formula $\kappa Q_{n}=n$
\end_inset
,
\begin_inset Formula $\kappa G\leq\delta G$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
\begin_inset Formula $\delta G$
\end_inset
je minimalna stopnja vozlišča v grafu
\begin_inset Formula $G$
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Pojasnite Whitney-ev izrek, ki katekterizira
\begin_inset Formula $2-$
\end_inset
povezane grafe.
Skicirajte dokaz tega izreka.
Zapišite Mengerjev izrek.
\end_layout
\begin_layout Definition*
Poti
\begin_inset Formula $\left[p_{1},p_{2},\dots,p_{n-1},p\right]$
\end_inset
in
\begin_inset Formula $\left[r_{1},r_{2},\dots,r_{m-1},r_{m}\right]$
\end_inset
sta notranje disjunktni, če sta disjunktni množici njunih vozlišč izvzemši
prvo in zadnje vozlišče.
\end_layout
\begin_layout Theorem*
Graf
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $\left|VG\right|\geq2$
\end_inset
, je
\begin_inset Formula $2-$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists$
\end_inset
notranje disjunktni
\begin_inset Formula $u,v-$
\end_inset
poti.
\end_layout
\begin_layout Proof
Dokazujemo ekvivalenco:
\end_layout
\begin_deeper
\begin_layout Description
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
Po predpostavki za poljubna
\begin_inset Formula $u,v$
\end_inset
obstajata dve notranje disjunktni
\begin_inset Formula $u,v-$
\end_inset
poti.
Dokazujemo, da je
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $2-$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow$
\end_inset
nima prereznega vozlišča
\begin_inset Formula $\Leftrightarrow$
\end_inset
ne obstaja prerezna množica, ki je singleton
\begin_inset Foot
status open
\begin_layout Plain Layout
množica moči ena
\end_layout
\end_inset
.
Dokažimo, da poljubno
\begin_inset Formula $x\in VG$
\end_inset
ni prerezno, torej da po odstranitvi tega vozlišča še vedno obstaja povezava
med poljubnima
\begin_inset Formula $u,v\in V\left(G-x\right)$
\end_inset
.
Ločimo 3 primere:
\begin_inset Formula $x$
\end_inset
je na prvi
\begin_inset Formula $u,v-$
\end_inset
poti,
\begin_inset Formula $x$
\end_inset
je na drugi
\begin_inset Formula $u,v-$
\end_inset
poti,
\begin_inset Formula $x$
\end_inset
ni na nobeni izmed
\begin_inset Formula $u,v-$
\end_inset
poti.
V vsakem primeru sta
\begin_inset Formula $u,v$
\end_inset
v
\begin_inset Formula $G-x$
\end_inset
še vedno v isti povezani komponenti.
\end_layout
\begin_layout Description
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
Po predpostavki je
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $2-$
\end_inset
povezan.
Vzemimo poljubna
\begin_inset Formula $u,v\in VG$
\end_inset
.
Indukcija po
\begin_inset Formula $d_{G}\left(u,v\right)$
\end_inset
:
\end_layout
\begin_deeper
\begin_layout Standard
Baza:
\begin_inset Formula $d_{G}\left(u,v\right)=1$
\end_inset
(sosednji vozlišči)
\begin_inset Formula $G-e$
\end_inset
je povezan, sicer je RAAPDD
\begin_inset Formula $uv$
\end_inset
most, kar bi bilo v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
s predpostavko, ker bi bil en izmed
\begin_inset Formula $u,v$
\end_inset
prerezno, saj ima
\begin_inset Formula $G$
\end_inset
vsaj 3 vozlišča in ima vsaj eden izmed
\begin_inset Formula $u,v$
\end_inset
še enega soseda.
Sedaj vemo, da
\begin_inset Formula $\exists u,v-$
\end_inset
pot, ki ni
\begin_inset Formula $uv$
\end_inset
.
Imamo torej dve notranje disjunktni
\begin_inset Formula $u,v-$
\end_inset
poti:
\begin_inset Formula $e$
\end_inset
in tisto drugo.
\end_layout
\begin_layout Standard
Korak:
\begin_inset Formula $d_{G}\left(u,v\right)=k\geq2$
\end_inset
.
Naj bo
\begin_inset Formula $P$
\end_inset
najkrajša
\begin_inset Formula $u,v-$
\end_inset
pot.
Predzadnje vozlišče na njej (tik pred
\begin_inset Formula $v$
\end_inset
) naj bo
\begin_inset Formula $w$
\end_inset
.
\begin_inset Formula $d_{G}\left(u,w\right)=k-1$
\end_inset
in po I.
P.
obstajata dve notranje disjunktni
\begin_inset Formula $u,w-$
\end_inset
poti
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
.
Ločimo primera:
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $v\in VR\cup VS$
\end_inset
Tedaj je
\begin_inset Formula $v$
\end_inset
na ciklu, ki ga tvorita poti
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
(je na eni izmed poti).
Zato obstajata dve notranje disjunktni
\begin_inset Formula $u,v-$
\end_inset
poti; ena v eno smer po ciklu, druga v drugo.
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $v\not\in VR\cup VS$
\end_inset
Tedaj
\begin_inset Formula $v$
\end_inset
ni na tem ciklu, vendar je sosed
\begin_inset Formula $w$
\end_inset
, ki je na ciklu.
\begin_inset Formula $G-w$
\end_inset
mora biti povezan, saj smo odstranili le eno vozlišče, torej
\begin_inset Formula $\exists u,v-$
\end_inset
pot
\begin_inset Formula $T$
\end_inset
.
Ločimo primera:
\end_layout
\begin_deeper
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $T\cap\left(VS\cup VR\right)=\left\{ u\right\} $
\end_inset
Našli smo dve notranje disjunktni poti v
\begin_inset Formula $G$
\end_inset
:
\begin_inset Formula $T$
\end_inset
in
\begin_inset Formula $\left[\dots R,v\right]$
\end_inset
(
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $wv$
\end_inset
povezava).
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left|T\cap\left(VS\cup VR\right)\right|\geq2$
\end_inset
Naj bo
\begin_inset Formula $x$
\end_inset
zadnje (kjer je
\begin_inset Formula $v$
\end_inset
konec poti) vozlišče na
\begin_inset Formula $T$
\end_inset
, ki je na
\begin_inset Formula $R\cup S$
\end_inset
.
BSŠ
\begin_inset Formula $x\in VS$
\end_inset
.
\begin_inset Formula $x\not=w$
\end_inset
po konstrukciji
\begin_inset Formula $T$
\end_inset
.
Dve poti: po
\begin_inset Formula $S$
\end_inset
do
\begin_inset Formula $x$
\end_inset
in nato po
\begin_inset Formula $T$
\end_inset
do
\begin_inset Formula $v$
\end_inset
ter
\begin_inset Formula $\left[\dots R,v\right]$
\end_inset
(
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $wv$
\end_inset
povezava).
\end_layout
\end_deeper
\end_deeper
\end_deeper
\begin_layout Theorem*
Menger (posplošitev Whitneya): naj bo
\begin_inset Formula $G$
\end_inset
graf z vsak
\begin_inset Formula $k+1$
\end_inset
vozlišči.
Tedaj je
\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
paroma notranje disjunktnih
\begin_inset Formula $u,v-$
\end_inset
poti.
\end_layout
\begin_layout Definition*
Graf je
\begin_inset Formula $k-$
\end_inset
povezan po povezavah, če
\begin_inset Formula $\nexists$
\end_inset
prerezna množica povezav moči
\begin_inset Formula $<k$
\end_inset
.
Povezanost grafa
\begin_inset Formula $G$
\end_inset
po povezavah (
\begin_inset Formula $\kappa'G$
\end_inset
) je največji
\begin_inset Formula $k$
\end_inset
, da je
\begin_inset Formula $G$
\end_inset
\begin_inset Formula $k-$
\end_inset
povezan po povezavah.
\end_layout
\begin_layout Theorem*
Menger':
\begin_inset Formula $G$
\end_inset
je
\begin_inset Formula $k-$
\end_inset
povezan po povezavah
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists k$
\end_inset
po povezavah notranje disjunktnih
\begin_inset Formula $u,v-$
\end_inset
poti.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Theorem*
\begin_inset Formula $\forall G\in\mathcal{G}:\kappa G\leq\kappa'G$
\end_inset
in
\begin_inset Formula $\kappa'G\leq\delta G$
\end_inset
.
\end_layout
\begin_layout Standard
Dokaze zadnjih treh izrekov najdete na magisteriju.
\end_layout
\begin_layout Subsection
Kaj je drevo in kaj je gozd? Katere katekterizacije dreves poznate?
\end_layout
\begin_layout Definition*
Gozd je graf brez ciklov.
Drevo je povezan gozd.
List je vozlišče stopnje 1.
\end_layout
\begin_layout Lemma
\begin_inset CommandInset label
LatexCommand label
name "lem:Vsako-drevo-z"
\end_inset
Vsako drevo z vsaj dvema vozliščema premore list.
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $T$
\end_inset
drevo,
\begin_inset Formula $v\in VT$
\end_inset
poljubno.
\begin_inset Formula $\left|VT\right|\geq2\wedge T$
\end_inset
povezan
\begin_inset Formula $\Rightarrow v$
\end_inset
ima soseda
\begin_inset Formula $v_{1}$
\end_inset
.
Če je
\begin_inset Formula $v_{1}$
\end_inset
edini sosed
\begin_inset Formula $v$
\end_inset
, je
\begin_inset Formula $v$
\end_inset
list, sicer je tudi
\begin_inset Formula $v_{2}\not=v_{1}$
\end_inset
sosed
\begin_inset Formula $v$
\end_inset
.
Če je
\begin_inset Formula $v$
\end_inset
edini sosed
\begin_inset Formula $v_{2}$
\end_inset
, je
\begin_inset Formula $v_{2}$
\end_inset
list, sicer je tudi
\begin_inset Formula $v_{3}$
\end_inset
sosed
\begin_inset Formula $v$
\end_inset
.
Postopek ponavljamo, dokler ne najdemo lista.
V grafu ni ciklov in graf je končen, zato se postopek ustavi.
\end_layout
\begin_layout Lemma
\begin_inset CommandInset label
LatexCommand label
name "lem:-drevo"
\end_inset
\begin_inset Formula $T$
\end_inset
drevo
\begin_inset Formula $\Rightarrow\left|ET\right|=\left|VT\right|-1$
\end_inset
\end_layout
\begin_layout Proof
z indukcijo po številu vozlišč:
\end_layout
\begin_layout Proof
Baza:
\begin_inset Formula $\left|VT=1\right|$
\end_inset
,
\begin_inset Formula $\left|EG\right|=0$
\end_inset
(izolirano vozlišče je drevo)
\end_layout
\begin_layout Proof
Korak:
\begin_inset Formula $T$
\end_inset
poljubno drevo
\begin_inset Formula $\left|VG\right|\geq2$
\end_inset
.
\begin_inset Formula $v\in VT$
\end_inset
naj bo list v
\begin_inset Formula $T$
\end_inset
po lemi
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:Vsako-drevo-z"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
Po I.
P.
je
\begin_inset Formula $\left|E\left(T-v\right)\right|=\left|V\left(T-v\right)\right|-1$
\end_inset
, po konstrukciji
\begin_inset Formula $T-v$
\end_inset
pa je
\begin_inset Formula $\left|E\left(T-v\right)\right|=\left|ET\right|-1$
\end_inset
,
\begin_inset Formula $\left|V\left(T-v\right)\right|=\left|VT\right|-1$
\end_inset
, torej
\begin_inset Formula $\left|ET\right|=\left|VT\right|-1$
\end_inset
.
\end_layout
\begin_layout Lemma
\begin_inset CommandInset label
LatexCommand label
name "lem:lema3drevesa-enaciklu-g-e-povezan"
\end_inset
\begin_inset Formula $G$
\end_inset
povezan,
\begin_inset Formula $e\in EG$
\end_inset
leži na ciklu
\begin_inset Formula $\Rightarrow G-e$
\end_inset
povezan.
\end_layout
\begin_layout Proof
Trdimo, da v
\begin_inset Formula $G-e\exists u,v-$
\end_inset
pot.
Ker je
\begin_inset Formula $G$
\end_inset
povezan,
\begin_inset Formula $\exists u,v-$
\end_inset
pot
\begin_inset Formula $P$
\end_inset
v
\begin_inset Formula $G$
\end_inset
.
Če
\begin_inset Formula $e\not\in P$
\end_inset
, ta pot obstaja tudi v
\begin_inset Formula $G-e$
\end_inset
.
Če
\begin_inset Formula $e\in P$
\end_inset
, očitno dobimo pot tako, da
\begin_inset Formula $e$
\end_inset
v
\begin_inset Formula $P$
\end_inset
nadomestimo s preostankom cikla, na katerem leži
\begin_inset Formula $e$
\end_inset
v
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Lemma
\begin_inset CommandInset label
LatexCommand label
name "lem:-povezan-."
\end_inset
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\Rightarrow\left|EG\right|\geq\left|VG\right|-1$
\end_inset
.
\end_layout
\begin_layout Proof
Če je
\begin_inset Formula $G$
\end_inset
drevo, velja enakost po lemi
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:-drevo"
plural "false"
caps "false"
noprefix "false"
\end_inset
, sicer
\begin_inset Formula $G$
\end_inset
premore cikel.
Po lemi
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:lema3drevesa-enaciklu-g-e-povezan"
plural "false"
caps "false"
noprefix "false"
\end_inset
\begin_inset Formula $\exists e\in EG\ni:G-e$
\end_inset
povezan.
Odstranjevanje povezav iz ciklov ponavljamo, dokler ne dobimo drevesa
\begin_inset Formula $T$
\end_inset
.
Velja
\begin_inset Formula $VT=VG$
\end_inset
(*) in
\begin_inset Formula $\left|ET\right|<\left|EG\right|$
\end_inset
(**).
Torej:
\begin_inset Formula $\left|VG\right|-1\overset{\text{(*)}}{=}\left|VT\right|-1\overset{\text{lema \ref{lem:-drevo}}}{=}\left|ET\right|\overset{\text{(**)}}{<}\left|EG\right|$
\end_inset
.
\end_layout
\begin_layout Theorem*
Karakterizacija dreves.
NTSE za graf
\begin_inset Formula $G$
\end_inset
:
\end_layout
\begin_deeper
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:-drevo"
\end_inset
\begin_inset Formula $G$
\end_inset
drevo
\end_layout
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:-pot-ZDB"
\end_inset
\begin_inset Formula $\forall u,v\in VG\exists!$
\end_inset
\begin_inset Formula $u,v-$
\end_inset
pot ZDB za vsak par vozlišč obstaja enolična pot
\end_layout
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:-povezan-"
\end_inset
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\wedge\forall e\in EG:e$
\end_inset
most
\end_layout
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:-povezan"
\end_inset
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\wedge\left|EG\right|=\left|VG\right|-1$
\end_inset
\end_layout
\end_deeper
\begin_layout Proof
Dokazujemo ekvivalenco:
\end_layout
\begin_deeper
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\ref{enu:-drevo}\Rightarrow\ref{enu:-pot-ZDB}\right)$
\end_inset
PDDRAA
\begin_inset Formula $\exists$
\end_inset
dve različni
\begin_inset Formula $u,v-$
\end_inset
poti za neka
\begin_inset Formula $u,v\in VG$
\end_inset
.
Tedaj graf premore cikel
\begin_inset Formula $\Rightarrow$
\end_inset
ni gozd
\begin_inset Formula $\Rightarrow$
\end_inset
ni drevo
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
.
PDDRAA
\begin_inset Formula $\nexists$
\end_inset
\begin_inset Formula $u,v-$
\end_inset
pot za neka
\begin_inset Formula $u,v\in VG\Rightarrow\Omega G\not=1\Rightarrow$
\end_inset
ni drevo
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
.
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\ref{enu:-pot-ZDB}\Rightarrow\ref{enu:-povezan-}\right)$
\end_inset
PDDRAA
\begin_inset Formula $\exists uv\in EG\ni:$
\end_inset
ni most
\begin_inset Formula $\Rightarrow\exists u,v-$
\end_inset
pot v
\begin_inset Formula $G-e\Rightarrow\exists$
\end_inset
dve različni
\begin_inset Formula $u,v-$
\end_inset
poti v
\begin_inset Formula $G$
\end_inset
(
\begin_inset Formula $uv$
\end_inset
in tista v
\begin_inset Formula $G-e$
\end_inset
)
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
.
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\ref{enu:-povezan-}\Rightarrow\ref{enu:-povezan}\right)$
\end_inset
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\Rightarrow G$
\end_inset
povezan velja vedno.
Dokažimo
\begin_inset Formula $\left|EG\right|=\left|VG\right|-1$
\end_inset
z indukcijo po številu vozlišč:
\end_layout
\begin_deeper
\begin_layout Standard
Baza: V
\begin_inset Formula $K_{2}$
\end_inset
je edina povezava most in
\begin_inset Formula $\left|EK_{2}\right|=2-1=1=\left|VK_{2}\right|$
\end_inset
\end_layout
\begin_layout Standard
Korak:
\begin_inset Formula $e\in EG$
\end_inset
poljuben:
\begin_inset Formula $\Omega\left(G-e\right)=2$
\end_inset
, dve komponenti
\begin_inset Formula $G-e$
\end_inset
naj bosta
\begin_inset Formula $G_{1}$
\end_inset
in
\begin_inset Formula $G_{2}$
\end_inset
.
Slednja sta povezana in za njiju velja, da je vsaka povezava most in sta
manjša grafa.
Po I.
P.
velja
\begin_inset Formula $\left|EG_{1}\right|=\left|VG_{1}\right|-1$
\end_inset
in
\begin_inset Formula $\left|EG_{2}\right|=\left|VG_{2}\right|-1$
\end_inset
.
Velja
\begin_inset Formula $\left|EG\right|=\left|EG_{1}\right|+\left|EG_{2}\right|+1=\left|VG_{1}\right|-1+\left|VG_{2}\right|-1+1=\left|VG_{1}\right|+\left|VG_{2}\right|-1=\left|VG\right|-1$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\ref{enu:-povezan}\Rightarrow\ref{enu:-pot-ZDB}\right)$
\end_inset
PDDRAA
\begin_inset Formula $G$
\end_inset
premore cikel
\begin_inset Formula $\overset{\text{lema \ref{lem:lema3drevesa-enaciklu-g-e-povezan}}}{\Rightarrow}$
\end_inset
če mu odstranimo povezavo s cikla, bo ostal povezan.
Obenem zaradi velja
\begin_inset Formula $\left|E\left(G-e\right)\right|=\left|V\left(G-e\right)\right|-2$
\end_inset
, kar je v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
z lemo
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:-povezan-."
plural "false"
caps "false"
noprefix "false"
\end_inset
(
\begin_inset Formula $G$
\end_inset
povezan, toda ne velja implikacija).
\end_layout
\end_deeper
\begin_layout Subsection
Kaj je vpeto drevo grafa? Kateri grafi premorejo vpeta drevesa? Kako lahko
rekurzivno določimo število vpetih dreves povezanega grafa?
\end_layout
\begin_layout Definition*
Podgraf
\begin_inset Formula $H$
\end_inset
grafa
\begin_inset Formula $G$
\end_inset
je vpet, če velja
\begin_inset Formula $VP=VG$
\end_inset
.
(Lahko pa ima ima
\begin_inset Formula $G$
\end_inset
povezave, ki jih
\begin_inset Formula $H$
\end_inset
nima).
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Vpeto drevo grafa
\begin_inset Formula $G$
\end_inset
je vpet podgraf, ki je drevo.
\end_layout
\begin_layout Theorem*
\begin_inset Formula $G$
\end_inset
povezan
\begin_inset Formula $\Leftrightarrow G$
\end_inset
premore vpeto drevo.
\end_layout
\begin_layout Proof
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
očitno.
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
: Če je
\begin_inset Formula $G$
\end_inset
drevo, je sam sebi vpeto drevo, sicer vsebuje cikel in iterativno uporabljamo
lemo
\begin_inset CommandInset ref
LatexCommand ref
reference "lem:lema3drevesa-enaciklu-g-e-povezan"
plural "false"
caps "false"
noprefix "false"
\end_inset
, dokler ne konstruiramo vpetega drevesa.
\end_layout
\begin_layout Definition*
\begin_inset Formula $\tau G$
\end_inset
naj bo število vpetih dreves grafa
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Remark*
\begin_inset Formula $T$
\end_inset
drevo
\begin_inset Formula $\Rightarrow\tau T=1$
\end_inset
,
\begin_inset Formula $\Omega G>1\Rightarrow\tau G=0$
\end_inset
,
\begin_inset Formula $\tau C_{n}=n$
\end_inset
\end_layout
\begin_layout Definition*
Z
\begin_inset Formula $G/e$
\end_inset
označimo skrčitev povezave
\begin_inset Formula $e$
\end_inset
v multigrafu
\begin_inset Foot
status open
\begin_layout Plain Layout
V multigrafu se ista povezava lahko pojavi večkrat.
\end_layout
\end_inset
\begin_inset Formula $G$
\end_inset
.
To je enako kot skrčitev povezave v grafu (
\begin_inset Formula $G\backslash e$
\end_inset
), le da ne odstranimo večkratnih vzporednih povezav.
\end_layout
\begin_layout Claim*
\begin_inset Formula $G$
\end_inset
povezan,
\begin_inset Formula $e\in EG\Rightarrow\tau G=\tau\left(G-e\right)+\tau\left(G/e\right)$
\end_inset
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $T$
\end_inset
vpeto drevo v
\begin_inset Formula $G$
\end_inset
.
Naj bo
\begin_inset Formula $e\in EG$
\end_inset
poljuben fiksen.
Vpetih dreves, za katere
\begin_inset Formula $e\not\in T$
\end_inset
, je
\begin_inset Formula $\tau\left(G-e\right)$
\end_inset
.
Vpetih dreves, za katere
\begin_inset Formula $e\in T$
\end_inset
, je
\begin_inset Formula $\tau\left(G/e\right)$
\end_inset
.
\end_layout
\begin_layout Standard
Rekurzivno torej določamo število vpetih dreves grafa z zgornjo trditvijo
tako, da izbiramo poljubne povezave in jih ožamo ter odstranjujemo in nato
seštejemo
\begin_inset Formula $\tau$
\end_inset
teh dveh operacij.
\end_layout
\begin_layout Subsection
Kaj je Laplaceova matrika multigrafa? Kaj pravi Kirchoffov izrek o številu
vpetih dreves multigrafa?
\end_layout
\begin_layout Definition*
Laplaceova matrika
\begin_inset Formula $LG$
\end_inset
je kvadratna matrika dimenzije
\begin_inset Formula $n$
\end_inset
, katere vrstice in stolpci so indeksirani z vozlišči multigrafa
\begin_inset Formula $G$
\end_inset
in velja
\begin_inset Formula
\[
LG_{ij}=\begin{cases}
\deg_{G}v & ;i=j\\
-\left(\text{število povezav med \ensuremath{v_{i}} in \ensuremath{v_{j}}}\right) & ;i\not=j
\end{cases}
\]
\end_inset
\end_layout
\begin_layout Theorem*
Kirchoff: Če je
\begin_inset Formula $G$
\end_inset
povezan multigraf, potem je
\begin_inset Formula $\tau G=\det\left(LG\text{ brez \ensuremath{i}tega stolpca in \ensuremath{i}te vrstice}\right)$
\end_inset
za poljuben
\begin_inset Formula $i$
\end_inset
.
ZDB
\begin_inset Formula $\tau G=\det LG_{i,i}$
\end_inset
.
\end_layout
\begin_layout Subsection
Kaj pomeni, da je graf Eulerjev? Kako karakteriziramo Eulerjeve grafe? Skicirajt
e dokaz slednjega rezultata.
\end_layout
\begin_layout Definition*
Sprehod v multigrafu je Eulerjev, če vsebuje vse povezave in sicer vsako
zgolj enkrat.
\series bold
Sklenjen
\series default
Eulerjev sprehod je Eulerjev obhod.
Graf je Eulerjev, če premore Eulerjev obhod.
\end_layout
\begin_layout Theorem*
\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 Proof
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
očitno.
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
:
\begin_inset Formula $\forall v\in VG:\deg_{G}v$
\end_inset
sod
\begin_inset Formula $\Rightarrow$
\end_inset
\begin_inset Formula $G$
\end_inset
premore cikel.
Indukcija po številu povezav:
\end_layout
\begin_layout Proof
Baza: Izolirano vozlišče, multigraf
\begin_inset Formula $VG=\left\{ u,v\right\} ,EG=\left\{ uv,uv\right\} $
\end_inset
in
\begin_inset Formula $C_{3}$
\end_inset
so vsi Eulerjevi.
\end_layout
\begin_layout Proof
Korak: Naj bo
\begin_inset Formula $\left|VG\right|\geq4$
\end_inset
.
\begin_inset Formula $G$
\end_inset
gotovo premore cikel
\begin_inset Formula $C$
\end_inset
, ker je povezan in nima listov (ni drevo).
Naj bo
\begin_inset Formula $H\coloneqq G-EC$
\end_inset
.
\begin_inset Formula $\forall u\in VC:\deg_{H}u=\deg_{G}u-2$
\end_inset
,
\begin_inset Formula $\forall u\not\in VC:\deg_{H}u=\deg_{G}u$
\end_inset
\begin_inset Formula $\Rightarrow\forall v\in H:\deg_{H}v$
\end_inset
sod
\begin_inset Formula $\Rightarrow$
\end_inset
vsaka komponenta
\begin_inset Formula $H$
\end_inset
je Eulerjev graf po I.
P., saj je manjši graf.
\begin_inset Formula $G$
\end_inset
je tudi Eulerjev, obhodimo ga lahko po ciklu
\begin_inset Formula $C$
\end_inset
; vsakič, ko naletimo na vozlišče, ki je del komponente
\begin_inset Formula $H$
\end_inset
, jo obhodimo in nadaljujemo pot po ciklu.
\end_layout
\begin_layout Paragraph*
Fleuryjev algoritem
\end_layout
\begin_layout Standard
sprejme graf in vrne obhod
\end_layout
\begin_layout Enumerate
Začnemo v poljubni povezavi
\end_layout
\begin_layout Enumerate
Ko povezavo prehodimo, jo izbrišemo
\end_layout
\begin_layout Enumerate
Postopek nadaljujemo in pri tem pazimo le na to, da gremo na most le v primeru,
če ni druge možnosti.
\end_layout
\begin_layout Theorem*
Če je
\begin_inset Formula $G$
\end_inset
Eulerjev graf, potem Fleuryjev algoritem vrne Eulerjev obhod.
\begin_inset Note Note
status open
\begin_layout Plain Layout
dodaj dekompozicijo in dekompozicijo v cikle
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Kdaj je graf Hamiltonov? Navedite in pojasnite potrebni pogoj z razpadom
grafa za obstoj Hamiltonovega cikla v grafu.
\end_layout
\begin_layout Definition*
\series bold
Hamiltonov cikel
\series default
v grafu je cikel, ki vsebuje vsa vozlišča grafa ZDB Hamiltonov cikel je
vpet podgraf, ki je cikel.
\series bold
Graf je Hamiltonov
\series default
, če premore Hamiltonov cikel.
\series bold
Hamiltonova pot
\series default
v grafu je pot, ki vsebuje vsa vozlišča grafa ZDB vpet podgraf, ki je pot.
\end_layout
\begin_layout Theorem*
\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
.
(potreben pogoj za obstoj Hamiltonovega cikla)
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $VG=\left\{ v_{1},\dots,v_{n}\right\} $
\end_inset
Hamiltonov.
BSŠ naj bo
\begin_inset Formula $\left[v_{1},\dots,v_{n}\right]$
\end_inset
Hamiltonov cikel.
Skica dokaza: Naj bosta
\begin_inset Formula $v_{i},v_{j}\in S,i<j$
\end_inset
.
Tedaj
\begin_inset Formula $G-S$
\end_inset
razbije
\begin_inset Formula $G$
\end_inset
na dva podgrafa:
\begin_inset Formula $K_{1}\left\{ v_{i+1},\dots,v_{j-1}\right\} $
\end_inset
in
\begin_inset Formula $K_{2}=\left(VG\cap\left\{ v_{i},v_{j}\right\} \right)\cap K_{1}=\left\{ v_{j+1},\dots,v_{n},v_{1},\dots,v_{i-1}\right\} $
\end_inset
.
Če
\begin_inset Formula $i=j-1$
\end_inset
, je ena podgraf prazen, če
\begin_inset Formula $n=3$
\end_inset
prav tako.
Podgrafa sta lahko povezana in tvorita skupno komponento, lahko pa nista
in tvorita dve komponenti.
Toda z odstranjevanjem
\begin_inset Formula $\left|S\right|$
\end_inset
vozlišč iz cikla lahko napravimo največ
\begin_inset Formula $\left|S\right|$
\end_inset
komponent.
\end_layout
\begin_layout Remark*
Izrek uporabimo v kontrapoziciji:
\begin_inset Formula $\exists S\subseteq VG\ni:\Omega\left(G-S\right)>\left|S\right|\Rightarrow G$
\end_inset
ni Hamiltonov.
\end_layout
\begin_layout Example*
\begin_inset Formula $G$
\end_inset
vsebuje prerezno vozlišče
\begin_inset Formula $\Rightarrow G$
\end_inset
ni Hamiltonov.
\end_layout
\begin_layout Claim*
\begin_inset Formula $K_{m,n}$
\end_inset
Hamiltonov
\begin_inset Formula $\Leftrightarrow m=n$
\end_inset
.
\end_layout
\begin_layout Proof
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
Uporabimo izrek o potrebnem pogoju.
RAAPDD BSŠ
\begin_inset Formula $m>n$
\end_inset
:
\begin_inset Formula $\Omega\left(G-n\right)=m$
\end_inset
, kar vodi v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
.
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
Očitno lahko skiciramo Hamiltonov cikel.
\end_layout
\begin_layout Claim*
\begin_inset Formula $G$
\end_inset
dvodelen z razdelitvijo
\begin_inset Formula $\left(A,B\right)$
\end_inset
,
\begin_inset Formula $\left|A\right|\not=\left|B\right|\Rightarrow G$
\end_inset
ni Hamiltonov.
\end_layout
\begin_layout Subsection
Navedite Orejev zadostni pogoj za obstoj Hamiltonovega cikla v grafu.
Skicirajte dokaz tega izreka.
\end_layout
\begin_layout Theorem*
Ore:
\begin_inset Formula $G$
\end_inset
graf,
\begin_inset Formula $\left|VG\right|\geq3$
\end_inset
,
\begin_inset Formula $\left(\forall u,v\in VG:uv\not\in EG\Rightarrow\deg u+\deg v\geq\left|VG\right|\right)\Rightarrow G$
\end_inset
Hamiltonov.
ZDB če za vsak par nesosednjih vozlišč v grafu z vsaj tremi vozlišči velja
\begin_inset Formula $\deg u+\deg v\geq\left|VG\right|$
\end_inset
, je graf Hamiltonov.
\end_layout
\begin_layout Proof
Dokaz z metodo najmanjšega protiprimera.
RAAPDD izrek ne velja.
Tedaj
\begin_inset Formula $\exists G$
\end_inset
, da predpostavka velja, zaključek pa ne.
Med vsemi takimi grafi izberimo tiste z najmanj vozlišči, izmed njih pa
enega izmed tistih, ki imajo največ povezav, in ga fiksiramo.
Naj bo to graf
\begin_inset Formula $G$
\end_inset
.
Zanj velja:
\end_layout
\begin_deeper
\begin_layout Itemize
\begin_inset Formula $\forall u,v\in VG:uv\not\in EG\Rightarrow\deg u+\deg v\geq\left|VG\right|$
\end_inset
\end_layout
\begin_layout Itemize
\begin_inset Formula $G$
\end_inset
ni Hamiltonov
\begin_inset Formula $\Rightarrow G$
\end_inset
gotovo ni polni graf
\begin_inset Formula $\Rightarrow\exists u,v\in VG\ni:uv\not\in EG$
\end_inset
.
Naj bo
\begin_inset Formula $H$
\end_inset
graf, da velja
\begin_inset Formula $VH\coloneqq VG$
\end_inset
in
\begin_inset Formula $EH\coloneqq EG\cup uv$
\end_inset
.
Zanj še vedno velja prejšnja točka, zaradi izbire
\begin_inset Formula $G$
\end_inset
(največ povezav) pa ni več protiprimer za izrek, zato je Hamiltonov.
Vsak Hamiltonov cikel v
\begin_inset Formula $H$
\end_inset
vsebuje
\begin_inset Formula $uv$
\end_inset
, sicer bi obstajal že v
\begin_inset Formula $G$
\end_inset
.
Vseeno pa
\begin_inset Formula $G$
\end_inset
premore Hamiltonovo pot, saj smo do cikla namreč dodali le eno povezavo.
Naj bo
\begin_inset Formula $\left[u=v_{1},v_{2},\dots,v_{n-1},v_{n}=v\right]$
\end_inset
Hamiltonov cikel v
\begin_inset Formula $H$
\end_inset
.
Vpeljimo množici
\begin_inset Formula $S=\left\{ v_{i},uv_{i+1}\in EG\right\} $
\end_inset
(ZDB predhodniki sosedov
\begin_inset Formula $u$
\end_inset
na Hamiltonovi poti v
\begin_inset Formula $G$
\end_inset
) in
\begin_inset Formula $T=\left\{ v_{i},vv_{i}\in EG\right\} $
\end_inset
(ZDB sosedje
\begin_inset Formula $v$
\end_inset
na Hamiltonovi poti v
\begin_inset Formula $G$
\end_inset
).
Velja
\begin_inset Formula $\left|S\cup T\right|=\left|S\right|+\left|T\right|-\left|S\cap T\right|$
\end_inset
, torej
\begin_inset Formula $\left|S\cup T\right|+\left|S\cup T\right|=\left|S\right|+\left|T\right|=\deg_{G}u+\deg_{G}v\overset{\text{predpostavka}}{\geq}\left|VG\right|=n$
\end_inset
.
Toda ker je
\begin_inset Formula $\left|S\cup T\right|=\left|VG\right|$
\end_inset
,
\begin_inset Formula $\left|S\cap T\right|\not=\emptyset$
\end_inset
, torej ima
\begin_inset Formula $v$
\end_inset
soseda iz
\begin_inset Formula $S$
\end_inset
(recimo mu
\begin_inset Formula $v_{i}$
\end_inset
), torej lahko konstruiramo Hamiltonov cikel v
\begin_inset Formula $G$
\end_inset
:
\begin_inset Formula $\left[u=v_{1},v_{2},\dots,v_{i},v_{n}=v,v_{n-1},\dots,v_{i+1},v_{1}=u\right]$
\end_inset
(
\begin_inset Formula $v_{i+1}$
\end_inset
je namreč po konstrukciji
\begin_inset Formula $S$
\end_inset
sosed
\begin_inset Formula $u$
\end_inset
), kar vodi v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Kaj-so-ravninski"
\end_inset
Kaj so ravninski grafi? Kaj so lica ravninske vložitve grafa in čemu je
enaka vsota dolžin vseh lic ravninske vložitve grafa? Kako lahko omejimo
število povezav ravninskega grafa s pomočjo njegove ožine?
\end_layout
\begin_layout Definition*
Graf
\begin_inset Formula $G$
\end_inset
ravninski
\begin_inset Formula $\Leftrightarrow$
\end_inset
lahko ga narišemo v ravnino tako, da se nobeni povezavi ne križata.
Ravninski graf skupaj z ustrezno risbo (vložitvijo) je graf, vložen v ravnino.
\end_layout
\begin_layout Example*
\begin_inset Formula $K_{2,3}$
\end_inset
je ravninski,
\begin_inset Formula $K_{3,3}$
\end_inset
ni ravninski.
\end_layout
\begin_layout Theorem*
Jordan: Sklenjena enostavna krivulja (t.
j.
taka, ki same sebe ne križa) v ravnini razdeli ravnino v notranjost, zunanjost
in krivuljo samo.
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $G$
\end_inset
ravninski, vložen v ravnino.
Sklenjena območja v ravnini, dobljena tako, da iz risbe odstranimo točke,
ki ustrezajo vozliščem in povezavam, imenujemo
\series bold
lica vložitve
\series default
.
S
\begin_inset Formula $FG$
\end_inset
označimo množico lič vložitve.
Seveda je tudi zunanje/neomejeno območje lice.
\end_layout
\begin_layout Example*
\begin_inset Formula $\left|FQ_{3}\right|=6$
\end_inset
\end_layout
\begin_layout Remark*
\begin_inset Formula $G$
\end_inset
lahko vložimo v ravnino
\begin_inset Formula $\Leftrightarrow$
\end_inset
lahko ga vložimo na sfero.
\end_layout
\begin_layout Definition*
Dolžina lica
\begin_inset Formula $F$
\end_inset
\begin_inset Formula $(\text{\ensuremath{\ell F}}),$
\end_inset
je število povezav, ki jih prehodimo, ko obhodimo lice\SpecialChar endofsentence
\end_layout
\begin_layout Remark*
Vsako drevo je ravninski graf.
Ima eno lice, katerega dolžina je
\begin_inset Formula $2\left|ET\right|$
\end_inset
.
\end_layout
\begin_layout Definition*
Ožina grafa
\begin_inset Formula $G$
\end_inset
,
\begin_inset Formula $gG$
\end_inset
, je dolžina najkrajšega cikla v
\begin_inset Formula $G$
\end_inset
.
Če je
\begin_inset Formula $G$
\end_inset
gozd, je
\begin_inset Formula $gG\coloneqq\infty$
\end_inset
.
\end_layout
\begin_layout Claim*
Če je
\begin_inset Formula $G$
\end_inset
ravninsli graf, vložen v ravnino, velja
\begin_inset Formula
\[
\sum_{F\in FG}\ell F=2\left|EG\right|
\]
\end_inset
\end_layout
\begin_layout Claim*
Naj
\begin_inset Formula $G$
\end_inset
premore cikel.
Naj bo
\begin_inset Formula $F\in FG$
\end_inset
.
\begin_inset Formula $\ell F\geq gG$
\end_inset
.
\begin_inset Formula $2\left|EG\right|=\sum_{F\in FG}\ell F\geq\sum_{F\in FG}gG=gG\left|FG\right|$
\end_inset
\end_layout
\begin_layout Claim*
Posledično: Če je
\begin_inset Formula $G$
\end_inset
ravninski graf z vsaj enim ciklom in je vložen v ravnino, je
\begin_inset Formula $\left|EG\right|\geq\frac{gG}{2}\left|FG\right|$
\end_inset
(*).
\end_layout
\begin_layout Subsection
Kaj pravi Eulerjeva formula za ravninske grafe? Skicirajte njen dokaz.
Katere posledice Eulerjeve formule poznate?
\end_layout
\begin_layout Theorem*
Eulerjeva formula: Če je
\begin_inset Formula $G$
\end_inset
ravninski vložen v ravnino, velja
\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=1+\Omega G$
\end_inset
.
\end_layout
\begin_layout Example*
Graf
\begin_inset Quotes gld
\end_inset
tri hiše
\begin_inset Quotes grd
\end_inset
:
\begin_inset Formula $\left|VG\right|=15$
\end_inset
,
\begin_inset Formula $\left|EG\right|=18$
\end_inset
,
\begin_inset Formula $\left|FG\right|=7$
\end_inset
,
\begin_inset Formula $\Omega G=3$
\end_inset
,
\begin_inset Formula $15+16+7=1+3$
\end_inset
\end_layout
\begin_layout Proof
Dokažimo najprej za povezan multigraf
\begin_inset Formula $G$
\end_inset
.
Dokazujemo
\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=2$
\end_inset
.
Indukcija po številu vozlišč:
\end_layout
\begin_layout Proof
Baza: Izolirano vozlišče:
\begin_inset Formula $\left|VG\right|=1$
\end_inset
,
\begin_inset Formula $\left|EG\right|=0+z$
\end_inset
,
\begin_inset Formula $\left|FG\right|=1+z$
\end_inset
, kjer je
\begin_inset Formula $z$
\end_inset
število zank (za navaden graf
\begin_inset Formula $z=0$
\end_inset
).
Drži.
\end_layout
\begin_layout Proof
Korak: Naj bo
\begin_inset Formula $e\in EG$
\end_inset
poljubna.
Skrčimo jo (kot v multigrafu).
\begin_inset Formula $\left|V\left(G/e\right)\right|=\left|VG\right|-1$
\end_inset
,
\begin_inset Formula $\left|E\left(G/e\right)\right|=\left|EG\right|-1$
\end_inset
,
\begin_inset Formula $\left|F\left(G/e\right)\right|=\left|FE\right|$
\end_inset
.
Velja
\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=2$
\end_inset
, saj po I.
P.
velja
\begin_inset Formula $\left|V\left(G/e\right)\right|+1-\left|E\left(G/e\right)\right|-1+\left|F\left(G/e\right)\right|=2$
\end_inset
.
\end_layout
\begin_layout Proof
Sedaj dokažimo še za nepovezan multigraf
\begin_inset Formula $G$
\end_inset
z
\begin_inset Formula $\Omega G$
\end_inset
komponentami.
Grafu lahko dodamo
\begin_inset Formula $\Omega G-1$
\end_inset
povezav, da ga povežemo, s čimer ne spremenimo niti
\begin_inset Formula $\left|FG\right|$
\end_inset
niti
\begin_inset Formula $\left|VG\right|$
\end_inset
.
Če je
\begin_inset Formula $E$
\end_inset
množica povezav, ki jo moramo dodati, velja
\begin_inset Formula $\left|VG\right|-\left|EG\cup E\right|+\left|FG\right|=2=\left|VG\right|-\left|EG\right|-\Omega G+1+\left|FG\right|\Rightarrow\left|VG\right|-\left|EG\right|+\left|FG\right|=2-1+\Omega G=1+\Omega G$
\end_inset
.
\end_layout
\begin_layout Theorem*
Za ravninski graf z vsaj tremi vozlišči velja
\begin_inset Formula $\left|EG\right|\leq3\left|VG\right|-6$
\end_inset
, če je slednji brez trikotnikov, a ima cikel, pa celo
\begin_inset Formula $\left|EG\right|\leq2\left|VG\right|-4$
\end_inset
.
\end_layout
\begin_layout Proof
Dokažimo za povezan ravninski graf, sicer mu lahko samo dodamo povezave
in ga povežemo.
Ločimo primera:
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(G\text{ drevo}\right)$
\end_inset
\begin_inset Formula $\left|EG\right|=\left|VG\right|-1$
\end_inset
(karakterizacija dreves)
\begin_inset Formula $\overset{?}{\leq}3\left|VG\right|-6$
\end_inset
.
Drži, kajti
\begin_inset Formula $\left|VG\right|\geq3$
\end_inset
.
\end_layout
\begin_deeper
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(G\text{ premore cikel}\right)$
\end_inset
Po Eulerjevi formuli velja
\begin_inset Formula
\[
2=\left|VG\right|-\left|EG\right|+\left|FG\right|\overset{\text{(*) iz \ref{subsec:Kaj-so-ravninski}}}{\leq}\left|VG\right|-\left|EG\right|+\frac{2\left|EG\right|}{gG}
\]
\end_inset
\begin_inset Formula
\[
2\leq\left|VG\right|-\left|EG\right|+\frac{2\left|EG\right|}{gG}
\]
\end_inset
\begin_inset Formula
\[
2-\left|VG\right|\leq\left|EG\right|\left(\frac{2}{gG}-1\right)\quad\quad\quad\quad/^{-1}
\]
\end_inset
\begin_inset Formula
\[
\left|VG\right|-2\geq\left|EG\right|\left(1-\frac{2}{gG}\right)=\left|EG\right|\left(\frac{gG-2}{gG}\right)
\]
\end_inset
\begin_inset Formula
\[
\left(\left|VG\right|-2\right)\frac{gG}{gG-2}\geq\left|EG\right|
\]
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Formula $\frac{gG}{gG-2}$
\end_inset
je največ 3 in to tedaj, ko graf premore trikotnik.
Če za vse večje
\begin_inset Formula $gG$
\end_inset
bo ta ulomek manjši, torej lahko levo stran omejimo navzdol:
\begin_inset Formula $3\left|VG\right|-6\geq\left(\left|VG\right|-2\right)\frac{gG}{gG-2}\geq\left|EG\right|$
\end_inset
\end_layout
\begin_layout Standard
Če pa graf ne premore trikotnika, a ima cikel, pa je
\begin_inset Formula $\frac{gG}{gG-2}=2$
\end_inset
in levo stran strožje omejimo navzgor in velja
\begin_inset Formula $2\left|VG\right|-4\geq\left|EG\right|$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Subsection
Kaj je kromatično število
\begin_inset Formula $\chi\left(G\right)$
\end_inset
grafa
\begin_inset Formula $G$
\end_inset
? Pojasnite požrešni algoritem barvanja grafa.
Kako lahko z njegovo pomočjo navzgor omejimo
\begin_inset Formula $\chi\left(G\right)$
\end_inset
?
\end_layout
\begin_layout Definition*
\begin_inset Formula $k-$
\end_inset
barvanje grafa
\begin_inset Formula $G$
\end_inset
je preslikava
\begin_inset Formula $C:VG\to\left\{ 1..k\right\} $
\end_inset
, za katero velja
\begin_inset Formula $uv\in EG\Rightarrow Cu\not=Cv$
\end_inset
.
Kromatično število
\begin_inset Formula $\chi G$
\end_inset
je najmanjši
\begin_inset Formula $k$
\end_inset
, za katerega najdemo
\begin_inset Formula $k-$
\end_inset
barvanje
\begin_inset Formula $G$
\end_inset
.
Za fiksen
\begin_inset Formula $i$
\end_inset
je
\begin_inset Formula $\left\{ u\in VG;Cu=i\right\} $
\end_inset
barvni razred, ki je neodvisna množica
\begin_inset Foot
status open
\begin_layout Plain Layout
Za neodvisno množico
\begin_inset Formula $S\subseteq VG$
\end_inset
velja
\begin_inset Formula $\forall u,v\in S:uv\not\in EG$
\end_inset
ZDB je
\begin_inset Quotes gld
\end_inset
brez povezav
\begin_inset Quotes grd
\end_inset
.
Glej vprašanje
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Kaj-je-neodvisnostno"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
\end_layout
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $\chi K_{n}=n$
\end_inset
,
\begin_inset Formula $\chi C_{n}=\begin{cases}
2 & ;n\text{ sod}\\
3 & ;n\text{ lih}
\end{cases}$
\end_inset
,
\begin_inset Formula $\chi P_{5,2}=3$
\end_inset
.
\end_layout
\begin_layout Definition*
Klično število grafa
\begin_inset Formula $G$
\end_inset
označimo z
\begin_inset Formula $\omega G$
\end_inset
.
Velja
\begin_inset Formula $\omega G=\left|VH\right|$
\end_inset
, kjer je
\begin_inset Formula $H$
\end_inset
največji poln podgraf v
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Remark*
\begin_inset Formula $\forall G\in\mathcal{G}:\chi G\geq\omega G$
\end_inset
.
\end_layout
\begin_layout Definition*
Požrešni algoritem barvanja: V poljubnem vrstnem redu zaporedno barvamo
vozlišča.
Posameznemu vozlišču priredimo najnižjo barvo, ki še ni uporabljena na
njegovih sosedih.
\end_layout
\begin_layout Fact*
Vedno
\begin_inset Formula $\exists$
\end_inset
vrstni red barvanja, da požrešni algoritem vrne barvanje s
\begin_inset Formula $\chi G$
\end_inset
barvami.
\end_layout
\begin_layout Claim*
\begin_inset Formula $\forall G\in\mathcal{G}:\chi G\leq\Delta G+1$
\end_inset
ZDB
\begin_inset Formula $\chi G$
\end_inset
je kvečjemu 1 večji od največje stopnje v grafu.
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $x_{1},\dots,x_{n}$
\end_inset
poljuben vrstni red vozlišč.
Poženemo požrešni algoritem.
Na poljubnem
\begin_inset Formula $i$
\end_inset
tem koraku, ko barvamo
\begin_inset Formula $x_{i}$
\end_inset
, je kvečjemu
\begin_inset Formula $\deg_{G}x_{i}$
\end_inset
barv, ki niso na razpolago, kar je
\begin_inset Formula $\leq\Delta G$
\end_inset
.
\end_layout
\begin_layout Claim*
\begin_inset Formula $G$
\end_inset
ni regularen
\begin_inset Formula $\Rightarrow\forall G\in\mathcal{G}:\chi G\leq\Delta G$
\end_inset
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $x$
\end_inset
tisto vozlišče, ki največje stopnje (*).
Vzamemo ga kot koren za BFS in z BFS vozlišča zmečemo v zaporedje
\begin_inset Formula $a$
\end_inset
.
Nato požrešno barvamo v obratni smeri, kot jo določa
\begin_inset Formula $a$
\end_inset
.
Na vsakem koraku, razen na korenu, bomo imeli soseda, ki še ni pobarvan,
torej je kvečjemu
\begin_inset Formula $\deg_{G}x_{i}-1$
\end_inset
barv, ki niso na razpolago, kar je
\begin_inset Formula $\leq\Delta G$
\end_inset
.
Na zadnjem koraku (koren) pa po predpostavki (*) na razpolago ni kvečjemu
\begin_inset Formula $\Delta G-1$
\end_inset
barv.
\end_layout
\begin_layout Theorem*
Brooks:
\begin_inset Formula $G$
\end_inset
povezan,
\begin_inset Formula $G$
\end_inset
niti poln niti lihi cikel
\begin_inset Formula $\Rightarrow\chi G\leq\Delta G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Theorem*
Naj bo
\begin_inset Formula $d_{1}\geq d_{2}\geq\cdots\geq d_{n}$
\end_inset
zaporedje stopenj grafa
\begin_inset Formula $G$
\end_inset
.
Tedaj velja
\begin_inset Formula $\chi G\leq1+\max_{i=1}^{n}\left(\min\left\{ d_{i},i-1\right\} \right)$
\end_inset
\end_layout
\begin_layout Proof
Poženimo požrešni algoritem barvanja v padajočem zaporedju stopenj.
Na
\begin_inset Formula $i$
\end_inset
tem barvamo vozlišče stopnje
\begin_inset Formula $d_{i}$
\end_inset
, zato imamo gotovo na voljo barvo iz
\begin_inset Formula $\left\{ 1..d_{i}+1\right\} $
\end_inset
.
Ker smo doslej pobarvali zgolj
\begin_inset Formula $i-1$
\end_inset
vozlišč, imamo gotovo na voljo barvo iz
\begin_inset Formula $\left\{ 1..i\right\} $
\end_inset
.
Algoritem pobarva vozlišče z barvo
\begin_inset Formula $\leq\min\left\{ i,d_{i}+1\right\} $
\end_inset
.
Največja uporabljena barva
\begin_inset Formula $k$
\end_inset
je
\begin_inset Formula $\leq\max_{i=1}^{n}\left\{ \min\left\{ d_{i}+1,i\right\} \right\} $
\end_inset
.
Torej
\begin_inset Formula $\chi G\leq1+\max_{i=1}^{n}\left(\min\left\{ d_{i},i-1\right\} \right)$
\end_inset
(izven
\begin_inset Formula $\max$
\end_inset
smo prišteli 1, znotraj
\begin_inset Formula $\min$
\end_inset
smo od vseh elementov 1 odšteli).
\begin_inset Note Note
status open
\begin_layout Plain Layout
TODO XXX FIXME dokaz in trditev za barvanje ravninskega grafa s petimi barvami
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Kaj je kromatični indeks
\begin_inset Formula $\chi'\left(G\right)$
\end_inset
grafa
\begin_inset Formula $G$
\end_inset
? Kaj pravi Vizingov izrek in kako na njegovi osnovi razdelimo vse grafe
v dva razreda?
\end_layout
\begin_layout Definition*
\begin_inset Formula $k-$
\end_inset
barvanje povezav je preslikava
\begin_inset Formula $C:EG\to\left\{ 1..k\right\} \ni:uv,uw\in EG\Rightarrow C\left(uv\right)\not=C\left(uw\right)$
\end_inset
.
ZDB povezavi s skupnim krajiščem dobita različni barvi.
Kromatični indeks grafa
\begin_inset Formula $G$
\end_inset
(oznaka
\begin_inset Formula $\chi'G$
\end_inset
) je najmanjši
\begin_inset Formula $k$
\end_inset
, za katerega
\begin_inset Formula $\exists k-$
\end_inset
barvanje grafa
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $\chi'C_{n}=\begin{cases}
2 & ;n\text{ sod}\\
3 & ;n\text{ lih}
\end{cases}$
\end_inset
\end_layout
\begin_layout Theorem*
Vizing:
\begin_inset Formula $\forall G\in\mathcal{G}:\Delta G\leq\chi'G\leq\Delta G+1$
\end_inset
.
\end_layout
\begin_layout Proof
Prvi neenačaj je očiten, drugega ne bomo dokazali.
\end_layout
\begin_layout Definition*
Graf
\begin_inset Formula $G$
\end_inset
je razreda I, če je
\begin_inset Formula $\chi'G=\Delta G$
\end_inset
oziroma razreda II, če je
\begin_inset Formula $\chi'G=\Delta G+1$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $C_{2n}$
\end_inset
so razreda
\begin_inset Formula $I$
\end_inset
,
\begin_inset Formula $C_{2n+1}$
\end_inset
so razreda II,
\begin_inset Formula $K_{3}$
\end_inset
je razreda II,
\begin_inset Formula $K_{4}$
\end_inset
je razreda
\begin_inset Formula $I$
\end_inset
\begin_inset Note Note
status open
\begin_layout Plain Layout
TODO XXX FIXME dokaz, da so dvodelni grafi I, K_2k razreda I in K_2k+1 razreda
II.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Kaj-je-neodvisnostno"
\end_inset
Kaj je neodvisnostno število grafa? Zanj podajte spodnjo mejo in zgornjo
mejo.
Opišite algoritem za izračun neodvisnostnega števila drevesa.
\end_layout
\begin_layout Definition*
Če je
\begin_inset Formula $G$
\end_inset
graf in
\begin_inset Formula $I\subseteq VG$
\end_inset
, je
\begin_inset Formula $I$
\end_inset
neodvisna
\begin_inset Formula $\Leftrightarrow\forall u,v\in I:uv\not\in EG$
\end_inset
ZDB če nobeni dve vozlišči v I nista sosednji v
\begin_inset Formula $G$
\end_inset
.
Moč največje neodvisne množice v
\begin_inset Formula $G$
\end_inset
je neodvisnostno število
\begin_inset Formula $G$
\end_inset
, označeno z
\begin_inset Formula $\alpha G$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $\alpha K_{n}=1$
\end_inset
,
\begin_inset Formula $\alpha C_{n}=\lfloor\frac{n}{2}\rfloor$
\end_inset
,
\begin_inset Formula $\alpha P_{5,2}=4$
\end_inset
\end_layout
\begin_layout Claim*
\begin_inset Formula $\forall G\in\mathcal{G}:\alpha G\cdot\chi G\geq\left|VG\right|$
\end_inset
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $\chi G=k$
\end_inset
in
\begin_inset Formula $V_{1},\dots,V_{k}$
\end_inset
barvni razredi nekega fiksnega barvanja s k barvami.
Slednji so neodvisne množice.
\begin_inset Formula $\forall i\in\left\{ 1..k\right\} :\left|V_{i}\right|\leq\alpha G\Rightarrow\left|VG\right|=\sum_{i=1}^{k}\left|V_{i}\right|\leq\sum_{i=1}^{k}\alpha G=\alpha G\cdot k=\alpha G\chi G$
\end_inset
\end_layout
\begin_layout Corollary*
Spodnja meja za neodvisnostno število
\begin_inset Formula $\alpha G\geq\frac{\left|VG\right|}{\chi G}$
\end_inset
.
\end_layout
\begin_layout Claim*
Zgornja meja za neodvisnostno število:
\begin_inset Formula $\alpha G\leq\left|VG\right|-\frac{\left|EG\right|}{\Delta G}$
\end_inset
.
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $I$
\end_inset
poljubna največja neodvisna množica v
\begin_inset Formula $G$
\end_inset
, torej
\begin_inset Formula $\left|I\right|=\alpha G$
\end_inset
.
V
\begin_inset Formula $VG\setminus I$
\end_inset
je vozlišč
\begin_inset Formula $\left|VG\right|-\alpha G$
\end_inset
.
Ker vozlišča v
\begin_inset Formula $I$
\end_inset
medsebojno niso povezana,
\begin_inset Formula $\left|EG\right|\leq\left(\left|VG\right|-\alpha G\right)\cdot\Delta G\Rightarrow\left|EG\right|\leq\left|VG\right|\Delta G-\alpha G\Delta G\Rightarrow\alpha G\Delta G\leq\left|VG\right|\Delta G-\left|EG\right|\Rightarrow\alpha G\leq\left|VG\right|-\frac{\left|EG\right|}{\Delta G}$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $Q_{d},d\geq1$
\end_inset
: Zgornja meja:
\begin_inset Formula $\alpha Q_{d}\leq\left|VQ_{d}\right|-\frac{\left|EQ_{d}\right|}{\Delta Q_{d}}=2^{d}-\frac{d2^{d-1}}{d}=2^{d}-2^{d-1}=2^{d-1}$
\end_inset
, Spodnja meja:
\begin_inset Formula $\alpha Q_{d}\geq\frac{\left|VQ_{d}\right|}{\chi Q_{d}}=\frac{2^{d}}{2}=2^{d-1}$
\end_inset
, torej
\begin_inset Formula $\alpha Q_{d}=2^{d-1}$
\end_inset
.
\end_layout
\begin_layout Paragraph*
Neodvisnostno število dreves
\end_layout
\begin_layout Standard
Naj bo
\begin_inset Formula $T$
\end_inset
drevo s poljubnim korenom
\begin_inset Formula $r\in VT$
\end_inset
.
Odslej na drevo glejmo
\begin_inset Formula $T$
\end_inset
kot na drevo s korenom
\begin_inset Formula $r$
\end_inset
.
Za neodvisno množico
\begin_inset Formula $S$
\end_inset
drevesa
\begin_inset Formula $T$
\end_inset
in poljubno vozlišče
\begin_inset Formula $x\in VT$
\end_inset
velja:
\begin_inset Formula $x\in S\Rightarrow$
\end_inset
potomci (otroci)
\begin_inset Formula $x\not\in S$
\end_inset
.
Če pa
\begin_inset Formula $x\not\in S$
\end_inset
, pa
\begin_inset Formula $S$
\end_inset
sme vsebovati potomce
\begin_inset Formula $x$
\end_inset
.
Z
\begin_inset Formula $Iv$
\end_inset
označimo velikost največje neodvisne množice s korenom v
\begin_inset Formula $v\in VT$
\end_inset
.
\end_layout
\begin_layout Standard
Očitno velja
\begin_inset Formula $\alpha T=Ir$
\end_inset
.
Z rekurzivnim postopkom določimo
\begin_inset Formula $\text{\ensuremath{\alpha T}}$
\end_inset
na tak način:
\begin_inset Formula
\[
\alpha T=Ir=\text{\ensuremath{\max}\left\{ 1+\sum_{v\in\text{vnuki/drugi potomci \ensuremath{r}}}Iv,\sum_{v\in\text{otroci/potomci }r}Iv\right\} }
\]
\end_inset
Formula je očitna.
Na vsakem rekurzivnem koraku lahko bodisi v množico izberemo
\begin_inset Formula $v$
\end_inset
in ne izberemo njegovih potomcev, bodisi izberemo potomce, njega pa ne.
Z rekurzivnim algoritmom preverimo vse možnosti.
\end_layout
\begin_layout Example*
\begin_inset Formula $\alpha T_{n}$
\end_inset
, kjer je
\begin_inset Formula $T_{n}$
\end_inset
polno dvojiško drevo globine
\begin_inset Formula $n\in\mathbb{N}_{0}$
\end_inset
: Vpeljimo zaporedje
\begin_inset Formula $a_{n}=\alpha T_{n}$
\end_inset
in velja:
\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}_{0}}=\left[1,2,5,10,21,42,\dots\right]$
\end_inset
.
\end_layout
\begin_layout Theorem*
\begin_inset Formula $a_{0}=1$
\end_inset
,
\begin_inset Formula $a_{1}=2$
\end_inset
, za
\begin_inset Formula $n\geq2$
\end_inset
:
\begin_inset Formula $a_{n}=\begin{cases}
2_{n-1}+1 & ;n\text{ sod}\\
2_{n-1} & ;n\text{ lih}
\end{cases}$
\end_inset
.
\end_layout
\begin_layout Proof
Z indukcijo.
Baza sta
\begin_inset Formula $a_{0}$
\end_inset
in
\begin_inset Formula $a_{1}$
\end_inset
.
Indukcijska predpostavka je dana v izreku.
ITD DOPIŠI DOKAZ.
\begin_inset Quotes gld
\end_inset
DS2P FMF 2024-04-18
\begin_inset Quotes grd
\end_inset
stran 5.
\end_layout
\begin_layout Subsection
\begin_inset CommandInset label
LatexCommand label
name "subsec:Kaj-je-dominacijsko"
\end_inset
Kaj je dominacijsko število grafa? Zanj podajte spodnjo mejo in zgornjo
mejo.
Kakšna je zveza med dominacijskim številom grafa in njegovega vpetega podgrafa?
\end_layout
\begin_layout Standard
Naj bo
\begin_inset Formula $G$
\end_inset
graf.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Neodvisna množica
\begin_inset Formula $G$
\end_inset
je maksimalna, če ni prava podmnožica kakšne neodvisne množice v
\begin_inset Formula $G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
\begin_inset Formula $N_{G}\left(u\right)\coloneqq\left\{ v;uv\in EG\right\} $
\end_inset
je soseščina vozlišča
\begin_inset Formula $u$
\end_inset
(sosedje
\begin_inset Formula $u$
\end_inset
v
\begin_inset Formula $G$
\end_inset
).
\begin_inset Formula $N_{G}\left[u\right]\coloneqq N_{G}\left(u\right)\cup\left\{ u\right\} $
\end_inset
je zaprta soseščina vozlišča
\begin_inset Formula $u$
\end_inset
.
\begin_inset Formula $N_{G}\left[D\right]=\bigcup_{u\in D}N_{G}\left[u\right]$
\end_inset
je zaprta soseščina množice vozlišč
\begin_inset Formula $D.$
\end_inset
\begin_inset Formula $D\subseteq VG$
\end_inset
dominira
\begin_inset Formula $X\subseteq VG\Leftrightarrow X\subseteq N_{G}\left[D\right]$
\end_inset
.
Če
\begin_inset Formula $D$
\end_inset
dominira
\begin_inset Formula $VG$
\end_inset
, pravimo, da je
\begin_inset Formula $D$
\end_inset
dominantna množica grafa
\begin_inset Formula $G$
\end_inset
.
ZDB
\begin_inset Formula $D$
\end_inset
dominantna množica
\begin_inset Formula $G\Leftrightarrow\forall u\in VG:u\in D\vee\exists x\in D\ni:xu\in EG$
\end_inset
ZDB vsako vozlišče je v
\begin_inset Formula $D$
\end_inset
ali pa ima soseda iz
\begin_inset Formula $D$
\end_inset
.
Moč najmanjše dominacijske množice za
\begin_inset Formula $G$
\end_inset
je dominacijsko število grafa
\begin_inset Formula $G$
\end_inset
, označeno z
\begin_inset Formula $\gamma G$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Remark*
Vsaka maksimalna neodvisna množica grafa je njegova dominantna množica.
\end_layout
\begin_layout Example*
\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_{5,2}=3$
\end_inset
.
\end_layout
\begin_layout Theorem*
Za vsak graf brez izoliranih vozlišč velja, da je
\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 Proof
Spodnja meja: Če je
\begin_inset Formula $G$
\end_inset
dominantna množica in
\begin_inset Formula $u\in D$
\end_inset
, potem
\begin_inset Formula $u$
\end_inset
dominira
\begin_inset Formula $\leq\deg_{G}u+1$
\end_inset
vozlišč, torej vsako vozlišče iz
\begin_inset Formula $D$
\end_inset
dominira kvečjemu
\begin_inset Formula $\Delta G+1$
\end_inset
vozlišč.
Ker
\begin_inset Formula $VG\subseteq N_{G}\left[D\right]$
\end_inset
(unija zaprtih okolic vozlišč iz dominantne množice prekrije cel graf),
je
\begin_inset Formula $\left|D\right|\geq\frac{\left|VG\right|}{\Delta G+1}$
\end_inset
, kajti
\begin_inset Formula $\left|VG\right|=\left|N_{G}\left[D\right]\right|=\left|\bigcup_{u\in D}N_{G}\left[u\right]\right|\leq\sum_{u\in D}N\left(u\right)\leq\sum_{u\in D}$
\end_inset
\begin_inset Formula $\left(\Delta G+1\right)=\gamma G\left(\Delta G+1\right)$
\end_inset
.
\end_layout
\begin_layout Proof
Zgornja meja: Naj bo
\begin_inset Formula $I$
\end_inset
poljubna maksimalna neodvisna množica.
Vemo, da je
\begin_inset Formula $I$
\end_inset
tedaj dominantna.
Če je
\begin_inset Formula $\left|I\right|\leq\frac{\left|VG\right|}{2}$
\end_inset
smo dokazali, sicer vzemimo njen komplement
\begin_inset Formula $I'\coloneqq VG\setminus I$
\end_inset
.
Trdimo, da je
\begin_inset Formula $I'$
\end_inset
dominantna.
Vzemimo poljubno
\begin_inset Formula $u\in G$
\end_inset
.
Če
\begin_inset Formula $u\in I'$
\end_inset
, dominira samega sebe, sicer, ker je
\begin_inset Formula $G$
\end_inset
brez izoliranih vozlišč, ima
\begin_inset Formula $u$
\end_inset
vsaj enega soseda, ker pa je
\begin_inset Formula $I$
\end_inset
neodvisna, je ta sosed v
\begin_inset Formula $I'$
\end_inset
, torej je
\begin_inset Formula $I'$
\end_inset
dominantna in ima
\begin_inset Formula $\leq\frac{\left|VG\right|}{2}$
\end_inset
vozlišč in velja
\begin_inset Formula $\gamma G\leq\min\left\{ \left|I\right|,\left|I'\right|\right\} \leq\frac{\left|VG\right|}{2}$
\end_inset
, kajti
\begin_inset Formula $I\cup I'=VG$
\end_inset
.
\end_layout
\begin_layout Example*
Enakost spodnje meje velja v
\begin_inset Formula $K_{n}$
\end_inset
,
\begin_inset Formula $C_{n}$
\end_inset
.
Enakost zgornje meje velja pri glavnikih
\begin_inset Formula $T_{n}$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Note Note
status open
\begin_layout Plain Layout
dodaj 2-pakiranje in 2-pakirno število
\begin_inset Formula $\rho$
\end_inset
!
\end_layout
\end_inset
\end_layout
\begin_layout Theorem*
Če je
\begin_inset Formula $H$
\end_inset
vpet podgraf
\begin_inset Formula $G$
\end_inset
, je
\begin_inset Formula $\gamma G\leq\gamma H$
\end_inset
.
\end_layout
\begin_layout Proof
Naj bo
\begin_inset Formula $D$
\end_inset
minimalna dominantna množica za
\begin_inset Formula $H$
\end_inset
.
\begin_inset Formula $\left|D\right|=\gamma H$
\end_inset
.
Tedaj je
\begin_inset Formula $D$
\end_inset
očitno tudi dominantna množica za
\begin_inset Formula $G$
\end_inset
.
Toda seveda se lahko zgodi, da je v
\begin_inset Formula $G$
\end_inset
moč najti manjšo dominantno množico kot v
\begin_inset Formula $H$
\end_inset
, ker ima
\begin_inset Formula $G$
\end_inset
lahko dodatne povezave.
\end_layout
\begin_layout Standard
\begin_inset Note Note
status open
\begin_layout Plain Layout
TODO XXX FIXME vpeto drevo in
\begin_inset Formula $\gamma$
\end_inset
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Kaj je dominacijsko število grafa in kaj je celotno dominacijsko število
grafa? Kakšna je zveza med njima? Kakšna je povezava med dominacijskim
številom grafa in kromatičnim številom komplementa?
\end_layout
\begin_layout Standard
Dominacijsko število grafa je definirano v vprašanju
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Kaj-je-dominacijsko"
plural "false"
caps "false"
noprefix "false"
\end_inset
.
\end_layout
\begin_layout Definition*
Dominantna množica
\begin_inset Formula $D$
\end_inset
grafa
\begin_inset Formula $G$
\end_inset
je povezana, če inducira povezan podgraf, neodvisna, če inducira podgraf
brez povezav in
\series bold
celotna
\series default
, če ima vsako vozlišče iz
\begin_inset Formula $VG$
\end_inset
soseda v
\begin_inset Formula $D$
\end_inset
(tudi vozlišča iz
\begin_inset Formula $D$
\end_inset
).
Velikost najmanjše povezane dominantne množice označimo z
\begin_inset Formula $\gamma_{c}G$
\end_inset
, neodvisne z
\begin_inset Formula $\gamma_{i}G$
\end_inset
in
\series bold
celotne
\series default
z
\begin_inset Formula $\gamma_{t}G$
\end_inset
(connected, independent in total).
\end_layout
\begin_layout Example*
\begin_inset Formula $\gamma_{t}K_{n}=2$
\end_inset
,
\begin_inset Formula $\gamma_{t}P_{n}=\lfloor\frac{n}{2}\rfloor+\lceil\frac{n}{2}\rceil-\lfloor\frac{n}{4}\rfloor$
\end_inset
(gledamo parčke, ki se dominirajo).
\end_layout
\begin_layout Theorem*
Za vsak graf brez izoliranih vozlišč velja
\begin_inset Formula $\gamma G\leq\gamma_{t}G\leq2\gamma G$
\end_inset
.
\end_layout
\begin_layout Proof
Spodnja meja je očitna, kajti biti celotna dominantna množica je strožji
pogoj kot biti dominantna množica.
Dokažimo
\begin_inset Formula $\gamma_{t}G\leq2\gamma G$
\end_inset
: Naj bo
\begin_inset Formula $D$
\end_inset
poljubna dominantna množica
\begin_inset Formula $G$
\end_inset
.
Vsakemu
\begin_inset Formula $x\in D$
\end_inset
priredimo nekega soseda od
\begin_inset Formula $x$
\end_inset
, recimo
\begin_inset Formula $x'$
\end_inset
in ga dodajmo v
\begin_inset Formula $\hat{D}$
\end_inset
, torej
\begin_inset Formula $\hat{D}=D\cup\left\{ x';x\in D\right\} $
\end_inset
, s čimer dominantno množico spremenimo v celotno tako, da ji kvečjemu podvojimo
število vozlišč.
\end_layout
\begin_layout Example*
Enakost spodnje meje se pojavi pri
\begin_inset Formula $\gamma C_{4}=\gamma_{t}C_{4}=2$
\end_inset
, neenakost pa pri recimo
\begin_inset Formula $\gamma G_{3}=2\not=4=\gamma_{t}Q_{3}$
\end_inset
.
\end_layout
\begin_layout Subsection
Kaj je grupoid, polgrupa, monoid, grupa? Kako v monoidu izračunamo inverz
produkta obrnljivih elementov? Kako definiramo potence v monoidu in kateri
računski zakoni veljajo zanje?
\end_layout
\begin_layout Definition*
Če uvedemo binarno operacijo
\begin_inset Formula $f$
\end_inset
na množici
\begin_inset Formula $A$
\end_inset
takole:
\begin_inset Formula $f:A\times A\to A,f$
\end_inset
preslikava, je par
\begin_inset Formula $\left(A,f\right)$
\end_inset
\series bold
grupoid
\series default
.
ZDB zahtevamo, da je operacija preslikava (domena je enaka definicijskemu
območju) in s tem zaprtost operacije.
Dvojiški operator
\begin_inset Formula $f\left(a,b\right)$
\end_inset
pišimo kot
\begin_inset Formula $a\cdot b$
\end_inset
.
\end_layout
\begin_layout Definition*
Če
\begin_inset Formula $\forall a,b,c\in A:\left(a\cdot b\right)\cdot c=a\cdot\left(b\cdot c\right)$
\end_inset
(asociativnost), pravimo, da je
\begin_inset Formula $\left(A,\cdot\right)$
\end_inset
\series bold
podgrupa
\series default
ZDB asocietiven grupoid.
\end_layout
\begin_layout Definition*
Enota je element
\begin_inset Formula $e\in A\ni:\forall a\in A:a\cdot e=e\cdot a=a$
\end_inset
.
Polgrupi z enoto pravimo
\series bold
monoid
\series default
.
\end_layout
\begin_layout Definition*
Monoidu, v katerem so vsi elementi obrnljivi, pravimo
\series bold
grupa
\series default
ZDB
\series bold
\begin_inset Formula $\forall a\in A\exists b\in A\ni:a\cdot b=b\cdot a=e$
\end_inset
\series default
.
\end_layout
\begin_layout Remark*
Ker so inverzi v monoidu enolični (dokaz pri LA), inverz
\begin_inset Formula $a$
\end_inset
označimo z
\begin_inset Formula $a^{-1}$
\end_inset
.
\end_layout
\begin_layout Example*
\begin_inset Formula $\left(\mathcal{G},\square\right)$
\end_inset
monoid,
\begin_inset Formula $\left(\mathbb{R}_{0}^{+}=\left\{ x\in\mathbb{R};x\geq0\right\} ,\max\right)$
\end_inset
monoid, množica vseh nizov/seznamov s concat operacijo je monoid.
\end_layout
\begin_layout Theorem*
Če sta
\begin_inset Formula $a$
\end_inset
in
\begin_inset Formula $b$
\end_inset
v monoidu obrnljiva, je obrnljiv tudi njun produkt in velja
\begin_inset Formula $\left(a\cdot b\right)^{-1}=b^{-1}\cdot a^{-1}$
\end_inset
.
\end_layout
\begin_layout Proof
\begin_inset Formula $\left(a\cdot b\right)\cdot\left(b^{-1}\cdot a^{-1}\right)=a\cdot\left(b\cdot b^{-1}\right)\cdot a^{-1}=a\cdot e\cdot a^{-1}=a\cdot a^{-1}=e$
\end_inset
in podobno
\begin_inset Formula $\left(b^{-1}a^{-1}\right)\left(ab\right)=e$
\end_inset
, torej
\begin_inset Formula $\left(b^{-1}a^{-1}\right)\left(ab\right)=\left(ab\right)\left(b^{-1}a^{-1}\right)=e\Rightarrow ab=\left(b^{-1}a^{-1}\right)$
\end_inset
po definiciji inverza.
\end_layout
\begin_layout Corollary*
Če so
\begin_inset Formula $a_{1},\dots,a_{k}$
\end_inset
obrnljivi elementi monoida, je
\begin_inset Formula $\left(a_{1}\cdots a_{k}\right)$
\end_inset
obrnljiv element monoida in velja
\begin_inset Formula $\left(a_{1}\cdots a_{k}\right)^{-1}=a_{k}^{-1}\cdots a_{1}^{-1}$
\end_inset
.
\end_layout
\begin_layout Proof
Dokaz z indukcijo: Baza:
\begin_inset Formula $k=2$
\end_inset
velja, Korak: predpostavimo
\begin_inset Formula $\left(a_{1}\cdots a_{k}\right)^{-1}=a_{k}^{-1}\cdots a_{1}^{-1}$
\end_inset
.
Množimo z desne z
\begin_inset Formula $a_{k+1}$
\end_inset
in smo dokazali.
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $\left(A,\cdot\right)$
\end_inset
monoid,
\begin_inset Formula $n\in\mathbb{N}_{0}$
\end_inset
.
\begin_inset Formula $a^{0}\coloneqq e$
\end_inset
,
\begin_inset Formula $a^{n}=a\cdot a^{n-1}$
\end_inset
za
\begin_inset Formula $n\geq1$
\end_inset
.
\end_layout
\begin_layout Corollary*
Velja torej
\begin_inset Formula $a^{n}a^{m}=a^{n+m}$
\end_inset
,
\begin_inset Formula $\left(a^{n}\right)^{m}=a^{nm}$
\end_inset
,
\begin_inset Formula $\left(a^{-1}\right)^{n}=a^{-1}\cdots n-\text{krat}\cdots a^{-1}=\left(a\cdots n-\text{krat}\cdots a\right)^{-1}=\left(a^{n}\right)^{-1}$
\end_inset
.
Torej za obrnljiv
\begin_inset Formula $a$
\end_inset
velja
\begin_inset Formula $\left(a^{n}\right)^{-1}=\left(a^{-1}\right)^{n}$
\end_inset
.
\begin_inset Note Note
status open
\begin_layout Plain Layout
dodaj podgrupe etc
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Kaj je red elementa v grupi? Kaj je pravilo krajšanja v grupi? Dokažite
ga.
Kako se pravilo krajšanja odraža v Cayleyevi tabeli grupe?
\end_layout
\begin_layout Definition*
Cayleyeva tabela za grupoid
\begin_inset Formula $\left(A,\cdot\right)$
\end_inset
je kvadratna tabela širine
\begin_inset Formula $\left|A\right|$
\end_inset
, kjer ima
\begin_inset Formula $i,j-$
\end_inset
ta celica vrednost
\begin_inset Formula $a_{i}\cdot a_{j}$
\end_inset
, kjer je
\begin_inset Formula $a_{k}$
\end_inset
\begin_inset Formula $k-$
\end_inset
ti element množice
\begin_inset Formula $A$
\end_inset
.
Pač izberemo si neko linearno urejenost
\begin_inset Formula $A$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $\left(G,\cdot\right)$
\end_inset
končna grupa in
\begin_inset Formula $a\in G$
\end_inset
.
Tedaj je red elementa
\begin_inset Formula $a$
\end_inset
najmanjši
\begin_inset Formula $n\in\mathbb{N}\ni:a^{n}=e$
\end_inset
.
\end_layout
\begin_layout Theorem*
Dirichletovo načelo:
\begin_inset Formula $\exists n,m\in\left[k+1\right],n\not=m:a^{n}=a^{m}$
\end_inset
\end_layout
\begin_layout Proof
BSŠ
\begin_inset Formula $n<m$
\end_inset
.
\begin_inset Formula $a^{n}=a^{m}\Rightarrow a^{n}\left(a^{m}\right)^{-1}=a^{m}\left(a^{m}\right)^{-1}\Rightarrow a^{n-m}=e$
\end_inset
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Theorem*
Pravilo krajšanja: Če je
\begin_inset Formula $G$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
Ko omenimo algebrajsko strukturo, občasno omenimo le množico, ko je iz konteksta
operacija implicitno znana.
\end_layout
\end_inset
grupa,
\begin_inset Formula $a,b,c\in G$
\end_inset
, velja
\begin_inset Formula $ab=ac\Rightarrow b=c$
\end_inset
in
\begin_inset Formula $ba=ca\Rightarrow b=c$
\end_inset
.
\end_layout
\begin_layout Proof
Množimo obe strani z leve ali desne z inverzom
\begin_inset Formula $a$
\end_inset
.
\end_layout
\begin_layout Corollary*
V Cayleyevi tabeli grupe se v vsaki vrstici in v vsakem stolpcu pojavijo
vsi elementi grupe.
\end_layout
\begin_layout Subsection
Kaj je permutacijska grupa? Kaj je simetrična grupa
\begin_inset Formula $S_{n}$
\end_inset
in kaj je alternirajoča grupa
\begin_inset Formula $A_{n}$
\end_inset
? Kaj pravi Cayleyev izrek (o univerzalnosti permutacijskih grup) in kakšna
je ideja njegovega dokaza?
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $A$
\end_inset
množica.
Permutacija
\begin_inset Formula $A$
\end_inset
je bijekcija
\begin_inset Formula $A\to A$
\end_inset
.
Permutacijska grupa je množica nekaj permutacij
\begin_inset Formula $A$
\end_inset
, ki ga komponiranje tvorijo grupo.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Simetrična grupa:
\begin_inset Formula $S_{n}\coloneqq\left\{ \pi;\pi:\left\{ 1..n\right\} \to\left\{ 1..n\right\} \text{ bijekcija}\right\} $
\end_inset
.
Alternirajoča grupa:
\begin_inset Formula $A_{n}\coloneqq\left\{ \pi\in S_{n};\pi\text{ soda}\right\} $
\end_inset
.
Permutacija je soda, če je v zapisu z disjunktnimi cikli vsota dolžin ciklov,
ki ji odštejemo število ciklov, soda.
\end_layout
\begin_layout Theorem*
\begin_inset Formula $\left|A_{n}\right|=\frac{n!}{2}$
\end_inset
.
\begin_inset Note Note
status open
\begin_layout Plain Layout
DOKAŽI TODO XXX FIXME
\end_layout
\end_inset
\end_layout
\begin_layout Definition*
Naj bosta
\begin_inset Formula $\left(G,\circ\right)$
\end_inset
in
\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
.
Če je
\begin_inset Formula $f$
\end_inset
tudi bijekcija, je
\begin_inset Formula $f:G\to H$
\end_inset
izomorfizem.
Grupi sta izomorfni, če obstaja izomorfizem med njima.
Tedaj pišemo
\begin_inset Formula $G\approx H$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Theorem*
Cayley: Vsaka grupa je izomorfna neki permutacijski grupi.
\end_layout
\begin_layout Proof
(skica dokaza) Naj bo
\begin_inset Formula $\left(G,\cdot\right)$
\end_inset
grupa.
Vsakemu elementu grupe priredimo preslikavo
\begin_inset Formula $g\in G\mapsto\alpha_{g}:G\to G$
\end_inset
, ki slika takole:
\begin_inset Formula $\forall x\in G:\alpha_{k}x=g\cdot x$
\end_inset
.
\begin_inset Formula $\alpha_{g}$
\end_inset
je permutacija
\begin_inset Formula $G$
\end_inset
, saj je bijektivna, ker velja pravilo krajšanja:
\begin_inset Formula $x\not=y\Rightarrow\alpha_{g}x\overset{\text{pravilo krajšanja}}{=}gx\not=gy=\alpha_{g}y$
\end_inset
.
\begin_inset Formula $\left\{ \alpha_{g};\forall g\in G\right\} $
\end_inset
tvori permutacijsko grupo, ki je izomorfna izvorni grupi:
\begin_inset Formula $\left(\left\{ \alpha_{g};\forall g\in G\right\} ,\circ\right)\approx\left(G,\cdot\right)$
\end_inset
.
\end_layout
\begin_layout Subsection
Kaj so odseki grupe
\begin_inset Formula $G$
\end_inset
po podgrupi
\begin_inset Formula $H$
\end_inset
? Kdaj je
\begin_inset Formula $aH=H$
\end_inset
in kdaj je
\begin_inset Formula $aH=Ha$
\end_inset
? Kaj je vsebina Lagrangeovega izreka o moči podgrup in končnih grup?
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $\left(G,\cdot\right)$
\end_inset
grupa in
\begin_inset Formula $H$
\end_inset
podgrupa
\begin_inset Note Note
status open
\begin_layout Plain Layout
prosim definiraj podgrupo
\end_layout
\end_inset
\begin_inset Formula $G$
\end_inset
.
Če je
\begin_inset Formula $a\in G$
\end_inset
, definiramo
\begin_inset Formula $aH=\left\{ ah,h\in H\right\} $
\end_inset
(desni odsek podgrupe
\begin_inset Formula $H$
\end_inset
) in
\begin_inset Formula $Ha=\left\{ ha,h\in H\right\} $
\end_inset
(levi odsek podgrupe
\begin_inset Formula $H$
\end_inset
).
\end_layout
\begin_layout Theorem*
Naj bo
\begin_inset Formula $G$
\end_inset
grupa in
\begin_inset Formula $a,b\in G$
\end_inset
in
\begin_inset Formula $H$
\end_inset
podgrupa
\begin_inset Formula $G$
\end_inset
.
Tedaj veljajo naslednje lastnosti:
\end_layout
\begin_deeper
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:"
\end_inset
\begin_inset Formula $a\in aH$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:-1"
\end_inset
\begin_inset Formula $aH=H\Leftrightarrow a\in H$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset Formula $aH=bH\nabla aH\cap bH=\emptyset$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset Formula $aH=bH\Leftrightarrow a^{-1}b\in H$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\left|aH\right|=\left|bH\right|$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:-2"
\end_inset
\begin_inset Formula $aH=Ha\Leftrightarrow H=aHa^{-1}$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset Formula $aH$
\end_inset
podgrupa
\begin_inset Formula $G\Leftrightarrow a\in H$
\end_inset
\end_layout
\end_deeper
\begin_layout Proof
Dokažimo trditve:
\end_layout
\begin_deeper
\begin_layout Enumerate
\begin_inset Formula $e\in H\Rightarrow a\cdot e=a\in aH$
\end_inset
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
\begin_inset Formula $a\overset{\ref{enu:}}{\in}aH=H\Rightarrow a\in H$
\end_inset
,
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
Najprej ena vsebovanost:
\begin_inset Formula $\forall x\in aH\exists h\in H\ni:x=ah$
\end_inset
, ker
\begin_inset Formula $a\in H$
\end_inset
, je po zaprtosti podgrupe
\begin_inset Formula $H$
\end_inset
\begin_inset Formula $ah=x\in H\Rightarrow aH\subseteq H$
\end_inset
.
Nato še druga vsebovanost:
\begin_inset Formula $\forall x\in H:a^{-1}x\in H\Rightarrow a\left(a^{-1}x\right)=x\in aH\Rightarrow H\subseteq aH$
\end_inset
.
\end_layout
\begin_layout Enumerate
Imejmo
\begin_inset Formula $aH$
\end_inset
,
\begin_inset Formula $bH$
\end_inset
.
Če je
\begin_inset Formula $aH=bH$
\end_inset
, smo dokazali, sicer
\begin_inset Formula $\exists x\in aH\cup bH$
\end_inset
.
Ker
\begin_inset Formula $x\in aH\Rightarrow\exists h'\in H\ni:x=ah'$
\end_inset
.
Ker
\begin_inset Formula $x\in bH\exists h''\in H\ni:x=bh''$
\end_inset
.
Toree velja
\begin_inset Formula $x=ah'=bh''$
\end_inset
.
Množimo s
\begin_inset Formula $h'^{-1}\Rightarrow a=bh''h'^{-1}\Rightarrow aH=bh''\left(h'^{-1}H\right)\overset{\ref{enu:-1}}{=}bh''H\overset{\ref{enu:-1}}{=}bH$
\end_inset
.
\end_layout
\begin_layout Enumerate
...
\end_layout
\begin_layout Enumerate
Očitno (pravilo krajšanja)
\end_layout
\begin_layout Enumerate
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
\begin_inset Formula $aH=Ha\Rightarrow aHa^{-1}=Haa^{-1}=H$
\end_inset
.
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
\begin_inset Formula $H=aHa^{-1}\overset{\cdot a^{-1}}{\Rightarrow}a^{-1}H=Ha$
\end_inset
.
Ker je
\begin_inset Formula $a\in aH$
\end_inset
, je v
\begin_inset Formula $a^{-1}\in aH$
\end_inset
(grupa), ker je
\begin_inset Formula $a^{-1}\in aH\cap a^{-1}H$
\end_inset
, je
\begin_inset Formula $aH=a^{-1}H$
\end_inset
, torej
\begin_inset Formula $a^{-1}H=Ha\Rightarrow aH=Ha$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Theorem*
Lagrange: Če je
\begin_inset Formula $G$
\end_inset
končna grupa in
\begin_inset Formula $H$
\end_inset
podgrupa
\begin_inset Formula $G$
\end_inset
, potem
\begin_inset Formula $\left|H\right|$
\end_inset
deli
\begin_inset Formula $\left|G\right|$
\end_inset
.
Nadalje je število levih/desnih odsekov po
\begin_inset Formula $H$
\end_inset
enako
\begin_inset Formula $\frac{\left|G\right|}{\left|H\right|}$
\end_inset
.
\end_layout
\begin_layout Proof
Naj bodo
\begin_inset Formula $a_{1}H,a_{2}H,\dots,a_{n}H$
\end_inset
različni odseki.
Tedaj
\begin_inset Formula $\left|G\right|\overset{\ref{enu:}}{=}\left|a_{1}H\cup\cdots\cup a_{n}H\right|\overset{\text{disjunktni odseki}}{=}\sum_{i=1}^{k}\left|a_{i}H\right|=k\left|H\right|\Rightarrow k=\frac{\left|G\right|}{\left|H\right|}$
\end_inset
.
\end_layout
\begin_layout Corollary*
Če je
\begin_inset Formula $G$
\end_inset
končna grupa in
\begin_inset Formula $a\in G$
\end_inset
, potem
\begin_inset Formula $\red a$
\end_inset
deli
\begin_inset Formula $\left|G\right|$
\end_inset
.
\end_layout
\begin_layout Proof
\begin_inset Formula $\left\langle a\right\rangle =\left\{ a^{k};k\in\mathbb{Z}\right\} =\left\{ e,a,\dots,a^{n-1}\right\} \overset{\text{Lagrange}}{\Rightarrow}\left\langle a\right\rangle $
\end_inset
je gotovo podgrupa
\begin_inset Formula $G\Rightarrow n$
\end_inset
deli
\begin_inset Formula $\left|G\right|$
\end_inset
.
\end_layout
\begin_layout Subsection
Kaj je podgrupa edinka? Navedite nekaj primerov podgrup edink.
Kaj je faktorska grupa
\begin_inset Formula $G/H$
\end_inset
in kaj pomeni, da je operacija v
\begin_inset Formula $G/H$
\end_inset
dobro definirana?
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $H$
\end_inset
podgrupa grupe
\begin_inset Formula $G$
\end_inset
.
Tedaj rečemo, da je
\begin_inset Formula $H$
\end_inset
podgrupa edinka, če velja
\begin_inset Formula $\forall a\in G:aH=Ha\overset{\ref{enu:-2}}{\Leftrightarrow}\forall a\in G:aHa^{-1}=H$
\end_inset
.
Oznaka:
\begin_inset Formula $H\triangleleft G$
\end_inset
.
Če sta
\begin_inset Formula $G$
\end_inset
in
\begin_inset Formula $\left\{ e\right\} $
\end_inset
, kjer je
\begin_inset Formula $e$
\end_inset
enota v
\begin_inset Formula $G$
\end_inset
, edini edinki
\begin_inset Formula $G$
\end_inset
, je
\begin_inset Formula $G$
\end_inset
enostavna.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Center grupe
\begin_inset Formula $G\sim ZG\coloneqq\left\{ a\in G;\forall x\in G:ax=xa\right\} $
\end_inset
ZDB taki elementi
\begin_inset Formula $G$
\end_inset
, ki komutirajo z vsemi.
\end_layout
\begin_layout Example*
V Abelovi grupi je vsaka podgrupa edinka.
\begin_inset Formula $SL_{2}\mathbb{R}\triangleleft GL_{2}\mathbb{R}$
\end_inset
\begin_inset Note Note
status open
\begin_layout Plain Layout
NAPIŠI KAJ JE TO SPECIAL LINEAR ITD
\end_layout
\end_inset
.
\begin_inset Formula $ZG\triangleleft G$
\end_inset
.
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $H\triangleleft G$
\end_inset
.
\begin_inset Formula $G/H\coloneqq\left\{ aH;a\in G\right\} $
\end_inset
.
V množico
\begin_inset Formula $G/H$
\end_inset
vpeljemo operacijo
\begin_inset Formula $\left(aH\right)\left(bH\right)=\left(ab\right)H$
\end_inset
(*).
\end_layout
\begin_layout Theorem*
Faktorske grupe: Če je
\begin_inset Formula $H\triangleleft G$
\end_inset
, je
\begin_inset Formula $G/H$
\end_inset
grupa za (*).
\end_layout
\begin_layout Proof
Dokazati notranjost, enoto, asociativnost in inverze je trivialno.
Treba je še dokazati dobro definiranost, t.
j.
\begin_inset Formula $a,a'$
\end_inset
iz istega odseka in
\begin_inset Formula $b,b'$
\end_inset
iz istega odseka
\begin_inset Formula $\Rightarrow\left(aH\right)\left(bH\right)=\left(ab\right)H=\left(a'b'\right)H=\left(a'H\right)\left(b'H\right)$
\end_inset
.
Ker
\begin_inset Formula $a'\in aH\Rightarrow\exists h'\in H\ni:ah'=a'$
\end_inset
.
Ker
\begin_inset Formula $b'\in bH\Rightarrow\exists h''\in H\ni:bh''=b'$
\end_inset
.
Sedaj
\begin_inset Formula $\left(a'H\right)\left(b'H\right)\overset{\text{def.}}{=}\left(a'b'\right)H=\left(ah'bh''\right)H=ah'b\left(h''H\right)\overset{\ref{enu:-1}}{=}ah'bH=ah'\left(bH\right)\overset{H\text{ edinka}}{=}ah'\left(Hb\right)=a\left(h'H\right)b\overset{\ref{enu:-1}}{=}aHb=\left(ab\right)H$
\end_inset
.
\end_layout
\begin_layout Subsection
Kaj je kolobar, kaj je cel kolobar? Kaj je pravilo krajšanja v kolobarjih
in kakšna je povezava tega pravila s celimi kolobarji? Kaj velja za končne
cele kolobarje?
\end_layout
\begin_layout Definition*
Bigrupoid
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
je kolobar, če je
\begin_inset Formula $\left(R,+\right)$
\end_inset
abelova grupa,
\begin_inset Formula $\left(R,\cdot\right)$
\end_inset
polgrupa in velja
\begin_inset Formula $\forall a,b,c\in R:a\cdot\left(b+c\right)=a\cdot b+a\cdot c\wedge\left(a+b\right)\cdot c=a\cdot c+b\cdot c$
\end_inset
(leva in desna distributivnost).
Kolobar je komutativen, če je
\begin_inset Formula $\left(R,\cdot\right)$
\end_inset
komutativna polgrupa.
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
je kolobar z enoto, če je
\begin_inset Formula $\left(R,\cdot\right)$
\end_inset
monoid.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Direktna vsota kolobarjev: Naj bosta
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
kolobarja.
\begin_inset Formula $R\oplus S=R\times S$
\end_inset
je direktna vsota .
Definirajmo operaciji
\begin_inset Formula $\left(r,s\right)+'\left(r',s'\right)\coloneqq\left(r+r',s+s'\right)$
\end_inset
,
\begin_inset Formula $\left(r,s\right)\cdot'\left(r',s'\right)\coloneqq\left(r\cdot r',s\cdot s'\right)$
\end_inset
.
\end_layout
\begin_layout Standard
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Center kolobarja
\begin_inset Formula $\sim ZR\coloneqq\left\{ a\in R;\forall x\in R:ax=xa\right\} $
\end_inset
, ZDB vsi taki elementi
\begin_inset Formula $R$
\end_inset
, ki pri množenju s poljubnim elementom kolobarja komutirajo.
\end_layout
\begin_layout Claim*
Če sta
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
kolobarja, je
\begin_inset Formula $\left(R\oplus S,+',\cdot'\right)$
\end_inset
kolobar.
Nadalje: Če sta
\begin_inset Formula $R$
\end_inset
in
\begin_inset Formula $S$
\end_inset
komutativna kolobara, je tudi
\begin_inset Formula $\left(R\oplus S,+',\cdot'\right)$
\end_inset
komutativen kolobar.
Če sta z enoto, je tudi
\begin_inset Formula $\left(R\oplus S,+',\cdot'\right)$
\end_inset
.
\begin_inset Note Note
status open
\begin_layout Plain Layout
DEFINIRAJ PODKOLOBAR
\end_layout
\end_inset
\end_layout
\begin_layout Definition*
Če v kolobarju
\begin_inset Formula $R$
\end_inset
velja
\begin_inset Formula $a\cdot b=0$
\end_inset
\begin_inset Foot
status open
\begin_layout Plain Layout
0 je aditivna enota
\end_layout
\end_inset
in sta
\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
\begin_inset Separator plain
\end_inset
\end_layout
\begin_layout Definition*
V kolobarju
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
velja pravilo krajšanja, če velja
\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 Separator plain
\end_inset
\end_layout
\begin_layout Definition*
Komutativen kolobar z enoto
\begin_inset Formula $1\not=0$
\end_inset
(ZDB multiplikativna enota ni enaka aditivni) brez deliteljev niča je
\series bold
cel
\series default
.
\end_layout
\begin_layout Example*
\begin_inset Formula $\left(\mathbb{Z},+,\cdot\right)$
\end_inset
je cel, toda
\begin_inset Formula $\left(\mathbb{Z}_{6},+_{6},\cdot_{6}\right)$
\end_inset
ni cel, ker premore delitelje niča.
\end_layout
\begin_layout Theorem*
Naj bo
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
komutativen kolobar z enoto
\begin_inset Formula $1\not=0$
\end_inset
.
Velja
\begin_inset Formula $R$
\end_inset
cel
\begin_inset Formula $\Leftrightarrow$
\end_inset
v
\begin_inset Formula $R$
\end_inset
velja pravilo krajšanja.
\end_layout
\begin_layout Proof
Dokazujemo ekvivalenco:
\end_layout
\begin_deeper
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\Rightarrow\right)$
\end_inset
Predpostavimo, da je
\begin_inset Formula $R$
\end_inset
cel.
Predpostavimo
\begin_inset Formula $ab=ac$
\end_inset
za poljuben
\begin_inset Formula $a\not=0$
\end_inset
in poljubna
\begin_inset Formula $b,c$
\end_inset
.
Računamo:
\begin_inset Formula $ab=ac\Leftrightarrow ab-ac=0\Leftrightarrow a\left(b-c\right)=0$
\end_inset
.
Ker je
\begin_inset Formula $R$
\end_inset
cel in
\begin_inset Formula $a\not=0$
\end_inset
, mora biti
\begin_inset Formula $b-c=0$
\end_inset
, sicer bi bila
\begin_inset Formula $a$
\end_inset
in
\begin_inset Formula $b-c$
\end_inset
delitelja niča, kar bi bilo v
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
s predpostavko o celosti
\begin_inset Formula $R$
\end_inset
.
\begin_inset Formula $b-c=0\Rightarrow b=c$
\end_inset
, torej
\begin_inset Formula $\forall a\not=0,b,c\in R:ab=ac\Rightarrow b=c\sim$
\end_inset
velja pravilo krajšanja.
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $\left(\Leftarrow\right)$
\end_inset
Predpostavimo, da v komutativnem kolobarju z enoto
\begin_inset Formula $1\not=0$
\end_inset
\begin_inset Formula $R$
\end_inset
velja pravilo krajšanja.
Predpostavimo
\begin_inset Formula $ab=0$
\end_inset
,
\begin_inset Formula $a\not=0$
\end_inset
.
Dokazati je treba
\begin_inset Formula $b=0$
\end_inset
, sicer bi imeli delitelje niča.
Velja
\begin_inset Formula $ab=0=a\cdot0$
\end_inset
.
Uporabimo pravilo krajšanja na
\begin_inset Formula $ab=a0$
\end_inset
in dobimo
\begin_inset Formula $b=0$
\end_inset
.
Kolobar je cel.
\end_layout
\end_deeper
\begin_layout Definition*
Komutativen kolobar
\begin_inset Formula $R$
\end_inset
z enoto
\begin_inset Formula $1\not=0$
\end_inset
je
\series bold
obseg
\series default
, če je vsak neničeln element obrnljiv v
\begin_inset Formula $\left(R,\cdot\right)$
\end_inset
ZDB
\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
\end_inset
je grupa.
Obseg
\begin_inset Formula $R$
\end_inset
je polje, če je
\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
\end_inset
abelova grupa ZDB
\begin_inset Formula $ZR=R$
\end_inset
.
\end_layout
\begin_layout Theorem*
Če je
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
končen cel kolobar
\begin_inset Formula $\Rightarrow R$
\end_inset
polje.
\end_layout
\begin_layout Proof
Dokažimo, da
\begin_inset Formula $\forall a\in R,a\not=0\exists a^{-1}\ni:aa^{-1}=1$
\end_inset
.
Naj bo
\begin_inset Formula $a\in R$
\end_inset
poljuben, z izjemo
\begin_inset Formula $a\not=0$
\end_inset
.
Oglejmo si
\begin_inset Formula $\left\{ a^{k};\forall k\geq0\right\} $
\end_inset
ZDB množico vseh potenc
\begin_inset Formula $a$
\end_inset
.
Ker
\begin_inset Formula $\left|R\right|<\infty\Rightarrow\exists i,j,$
\end_inset
BSŠ
\begin_inset Formula $i>j\ni a^{i}=a^{j}$
\end_inset
ZDB ker je
\begin_inset Formula $R$
\end_inset
končen, se nek element
\begin_inset Quotes gld
\end_inset
ponovi
\begin_inset Quotes grd
\end_inset
.
\begin_inset Formula $a^{j}\cdot a^{i-j}=a^{i}=a^{j}=a^{j}\cdot1$
\end_inset
Ker je kolobar cel,
\begin_inset Formula $a^{j}\not=0$
\end_inset
in ker velja pravilo krajšanja,
\begin_inset Formula $a^{i-j}=1$
\end_inset
, pri čemer vemo, da je
\begin_inset Formula $i-j>0$
\end_inset
.
Ločimo dva primera:
\end_layout
\begin_deeper
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $i-j=1$
\end_inset
\begin_inset Formula $a=1\Rightarrow a$
\end_inset
je kot multiplikativna enota multiplikativni inverz sam sebi
\end_layout
\begin_layout Labeling
\labelwidthstring 00.00.0000
\begin_inset Formula $i-j>1$
\end_inset
\begin_inset Formula $a=a\cdot a^{i-j-1}=1$
\end_inset
, torej
\begin_inset Formula $a^{i-j-1}$
\end_inset
je inverz
\begin_inset Formula $a$
\end_inset
.
\end_layout
\end_deeper
\begin_layout Subsection
Kaj je karakteristika kolobarja? Kako lahko določimo karakteristiko kolobarja
z enoto? Kaj lahko povemo o karakteristiki celega kolobarja?
\end_layout
\begin_layout Definition*
Karakteristika kolobarja
\begin_inset Formula $R\sim\karakteristika R$
\end_inset
je najmanjši
\begin_inset Formula $n\in\mathbb{N}\ni:\forall a\in R:a+\cdots_{n-\text{krat}}\cdots+a=0$
\end_inset
.
Če tak
\begin_inset Formula $n$
\end_inset
ne obstaja, pravimo
\begin_inset Formula $\karakteristika R=0$
\end_inset
.
\end_layout
\begin_layout Theorem*
Naj bo
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
kolobar z enoto.
\begin_inset Formula $\karakteristika R=\red1$
\end_inset
v grupi
\begin_inset Formula $\left(R,+\right)$
\end_inset
ZDB red enote v aditivni grupi.
\end_layout
\begin_layout Proof
Po definiciji reda je
\begin_inset Formula $1+\cdots_{\red1-\text{krat}}\cdots+1=0$
\end_inset
in za nek
\begin_inset Formula $m<\red1$
\end_inset
\begin_inset Formula $1+\cdots_{m-\text{krat}}\cdots+1\not=0$
\end_inset
, torej
\begin_inset Formula $\karakteristika R\geq\red1$
\end_inset
.
Sedaj vzemimo poljuben
\begin_inset Formula $a\in R$
\end_inset
.
Velja
\begin_inset Formula $a+\cdots_{\red1-\text{krat}}\cdots+a=1\cdot a+\cdots_{\red1-\text{krat}}\cdots+1\cdot a=a\cdot\left(1+\cdots_{\red1-\text{krat}}\cdots+1\right)=a\cdot0=0$
\end_inset
, torej
\begin_inset Formula $\karakteristika R\leq\red1$
\end_inset
, torej
\begin_inset Formula $\karakteristika R=\red1$
\end_inset
.
\end_layout
\begin_layout Theorem*
Naj bo
\begin_inset Formula $\left(R,+,\cdot\right)$
\end_inset
cel kolobar.
Tedaj velja bodisi
\begin_inset Formula $\karakteristika R=0$
\end_inset
bodisi
\begin_inset Formula $\karakteristika R=p$
\end_inset
, kjer je
\begin_inset Formula $p$
\end_inset
praštevilo.
\end_layout
\begin_layout Proof
Če je
\begin_inset Formula $\karakteristika R=0$
\end_inset
, smo dokazali, sicer je
\begin_inset Formula $\karakteristika R=r>0$
\end_inset
.
PDDRAA
\begin_inset Formula $n=pq$
\end_inset
za
\begin_inset Formula $p,q>1$
\end_inset
in
\begin_inset Formula $p,q\in\mathbb{N}$
\end_inset
.
Po prejšnjem izreku
\begin_inset Formula $\karakteristika R=\red1=n$
\end_inset
.
Tedaj velja
\begin_inset Formula $0=1+\cdots_{n-\text{krat}}\cdots+1=1+\cdots_{pq-\text{krat}}\cdots+1=\left(1+\cdots_{p-\text{krat}}\cdots+1\right)\cdot\left(1+\cdots_{q-\text{krat}}\cdots+1\right)=a\cdot b$
\end_inset
.
Ker smo v celem kolobarju, je bodisi
\begin_inset Formula $a=0$
\end_inset
, bodisi
\begin_inset Formula $b=0$
\end_inset
, toda to je
\begin_inset Formula $\rightarrow\!\leftarrow$
\end_inset
, saj bi bil potem
\begin_inset Formula $\red1=q$
\end_inset
ali
\begin_inset Formula $\red1=p$
\end_inset
, oboje pa je
\begin_inset Formula $<pq$
\end_inset
.
\end_layout
\begin_layout Subsection
Kaj je ideal kolobarja? Kako lahko preverimo, ali je
\begin_inset Formula $I\subseteq R$
\end_inset
ideal kolobarja
\begin_inset Formula $R$
\end_inset
? Kaj je faktorski kolobar
\begin_inset Formula $R/I$
\end_inset
in kako računamo v njem?
\end_layout
\begin_layout Definition*
Če je
\begin_inset Formula $R$
\end_inset
kolobar, je njegov podkolobar
\begin_inset Formula $S$
\end_inset
ideal, če velja
\begin_inset Formula $\forall v\in R,s\in S:rs,sr\in S$
\end_inset
ZDB to je podkolobar, zaprt za zunanje množenje.
\end_layout
\begin_layout Example*
\begin_inset Formula $n\cdot\mathbb{Z}$
\end_inset
(večkratniki
\begin_inset Formula $n$
\end_inset
) za fiksen
\begin_inset Formula $n$
\end_inset
so ideal v
\begin_inset Formula $\mathbb{Z}$
\end_inset
.
\begin_inset Formula $\mathbb{Z}$
\end_inset
je podkolobar v
\begin_inset Formula $\mathbb{Q}$
\end_inset
, toda ni njegov ideal.
\end_layout
\begin_layout Claim*
\begin_inset Formula $I\subseteq R$
\end_inset
je ideal
\begin_inset Formula $\Leftrightarrow0\in I$
\end_inset
(vsebuje aditivno enoto)
\begin_inset Formula $\wedge\forall i,j\in I:i-j\in I$
\end_inset
(zaprt za odštevanje)
\begin_inset Formula $\wedge\forall i\in I,r\in R:ir\in I,ri\in I$
\end_inset
(zaprt za zunanje množenje)
\begin_inset Note Note
status open
\begin_layout Plain Layout
TODO XXX FIXME vsota in produkt idealov je spet ideal
\end_layout
\end_inset
\end_layout
\begin_layout Definition*
Naj bo
\begin_inset Formula $R$
\end_inset
kolobar in
\begin_inset Formula $I$
\end_inset
ideal v
\begin_inset Formula $R$
\end_inset
.
Faktorski kolobar:
\begin_inset Formula $R/I=\left\{ a+I,\forall a\in R\right\} =\left\{ \left\{ a+i;\forall i\in I\right\} ;\forall a\in R\right\} $
\end_inset
vsebuje aditivne odseke.
V
\begin_inset Formula $R/I$
\end_inset
vpeljemo operaciji:
\begin_inset Formula $\left(a+I\right)+'\left(b+I\right)=a+b+I$
\end_inset
in
\begin_inset Formula $\left(a+I\right)\cdot'\left(b+I\right)=a\cdot b+I$
\end_inset
.
\end_layout
\begin_layout Theorem*
Če je
\begin_inset Formula $I$
\end_inset
ideal v
\begin_inset Formula $R$
\end_inset
, je
\begin_inset Formula $\left(R/I,+',\cdot'\right)$
\end_inset
kolobar.
\end_layout
\end_body
\end_document
