MAT1030 – Diskret matematikk Forelesning 22: Grafteori Roger Antonsen
351
0
0
Fulltekst
(2) Repetisjon og mer motivasjon. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(3) Repetisjon og mer motivasjon. Først litt repetisjon. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(4) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(5) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer.. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(6) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(7) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(8) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(9) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(10) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(11) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter, enkle grafer. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(12) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter, enkle grafer og komplette grafer.. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(13) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter, enkle grafer og komplette grafer. Hver node har en grad.. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(14) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter, enkle grafer og komplette grafer. Hver node har en grad. Summen av gradene til alle nodene i en graf er lik 2 ganger antallet kanter.. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(15) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter, enkle grafer og komplette grafer. Hver node har en grad. Summen av gradene til alle nodene i en graf er lik 2 ganger antallet kanter. Håndhilselemmaet: Det er alltid et partall antall noder av odde grad i en graf.. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(16) Repetisjon og mer motivasjon. Først litt repetisjon En graf består av noder og kanter Kanter ligger inntil noder, og noder kan være naboer. Vi bør kjenne til begrepene om sammenhengende grafer, tomme grafer, løkker, parallelle kanter, enkle grafer og komplette grafer. Hver node har en grad. Summen av gradene til alle nodene i en graf er lik 2 ganger antallet kanter. Håndhilselemmaet: Det er alltid et partall antall noder av odde grad i en graf.. Vi skal kjenne til komplementet av en graf og matriserepresentasjoner.. MAT1030 – Diskret matematikk. 14. april 2008. 2.
(17) Repetisjon og mer motivasjon. MAT1030 – Diskret matematikk. 14. april 2008. 3.
(18) Repetisjon og mer motivasjon. Grafer kan brukes til å representere omtrent alt som fins av relasjoner.. MAT1030 – Diskret matematikk. 14. april 2008. 3.
(19) Repetisjon og mer motivasjon. Grafer kan brukes til å representere omtrent alt som fins av relasjoner. Mange algoritmer/egenskaper kan forstås bedre ved å bruke grafer.. MAT1030 – Diskret matematikk. 14. april 2008. 3.
(20) Repetisjon og mer motivasjon. Grafer kan brukes til å representere omtrent alt som fins av relasjoner. Mange algoritmer/egenskaper kan forstås bedre ved å bruke grafer. Ofte er løsningen å kunne identifisere et problem som et grafteorisk problem.. MAT1030 – Diskret matematikk. 14. april 2008. 3.
(21) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(22) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset.. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(23) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk.. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(24) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form).. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(25) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold.. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(26) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(27) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv – det er altså en en-til-en-korrespondanse. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(28) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv – det er altså en en-til-en-korrespondanse – og som bevarer bestemte egenskaper.. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(29) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv – det er altså en en-til-en-korrespondanse – og som bevarer bestemte egenskaper. Intuitivt, så sier vi at to matematiske objekter er isomorfe hvis de er “strukturelt like”.. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(30) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv – det er altså en en-til-en-korrespondanse – og som bevarer bestemte egenskaper. Intuitivt, så sier vi at to matematiske objekter er isomorfe hvis de er “strukturelt like”. Hvis vi har tegnet opp to grafer og kan komme fra den ene grafen til den andre ved kun å flytte på noder og endre på lengdene på kantene, så er grafene isomorfe.. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(31) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv – det er altså en en-til-en-korrespondanse – og som bevarer bestemte egenskaper. Intuitivt, så sier vi at to matematiske objekter er isomorfe hvis de er “strukturelt like”. Hvis vi har tegnet opp to grafer og kan komme fra den ene grafen til den andre ved kun å flytte på noder og endre på lengdene på kantene, så er grafene isomorfe. Vi har ikke lov til å legge til eller ta bort noder eller kanter, eller dele kanter eller noder i to.... MAT1030 – Diskret matematikk. 14. april 2008. 4.
(32) Grafisomorfier Vi skal nå møte begrepet isomorfi for første gang i dette kurset. Isomorfibegrepet er veldig generelt og brukes overalt i matematikk. Ordet kommer fra gresk og betyr formlik (iso = lik, morf = form). Isomorfe objekter skal ha samme form, men kan ha ulikt innhold. En isomorfi er en funksjon som er injektiv og surjektiv – det er altså en en-til-en-korrespondanse – og som bevarer bestemte egenskaper. Intuitivt, så sier vi at to matematiske objekter er isomorfe hvis de er “strukturelt like”. Hvis vi har tegnet opp to grafer og kan komme fra den ene grafen til den andre ved kun å flytte på noder og endre på lengdene på kantene, så er grafene isomorfe. Vi har ikke lov til å legge til eller ta bort noder eller kanter, eller dele kanter eller noder i to... Følgende to grafer er isomorfe. MAT1030 – Diskret matematikk. 14. april 2008. 4.
(33) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 5.
(34) Grafisomorfier. b0. b1 a0. a1. a3. a2. b3. MAT1030 – Diskret matematikk. b2. 14. april 2008. 5.
(35) Grafisomorfier. b0. b1. b0. b1. a0. a1. a3. a2. a3. a2. a0. a1. b3. MAT1030 – Diskret matematikk. b2. b3. 14. april 2008. b2. 5.
(36) Grafisomorfier. b0. b1. b0. b1. a0. a1. a3. a2. a3. a2. a0. a1. b3. b2. b3. b2. Disse to grafene er også isomorfe med følgende grafer.. MAT1030 – Diskret matematikk. 14. april 2008. 5.
(37) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 6.
(38) Grafisomorfier. MAT1030 – Diskret matematikk. b3. a1. a2. b0. b1. a3. a0. b2. 14. april 2008. 6.
(39) Grafisomorfier. b2. b3. a1. a2. b0. b1. a3. a0. MAT1030 – Diskret matematikk. 14. april 2008. 6.
(40) Grafisomorfier. b2. MAT1030 – Diskret matematikk. b3. a1. a2. b0. b1. a3. 14. april 2008. a0. 6.
(41) Grafisomorfier. b2. MAT1030 – Diskret matematikk. b3. a3. a2. b0. b1. a1. 14. april 2008. a0. 6.
(42) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 7.
(43) Grafisomorfier. De neste par grafene er også er isomorfe med disse.. MAT1030 – Diskret matematikk. 14. april 2008. 7.
(44) Grafisomorfier. De neste par grafene er også er isomorfe med disse. a0 b0. b1. a3. a1. b3. b2 a2. MAT1030 – Diskret matematikk. 14. april 2008. 7.
(45) Grafisomorfier. De neste par grafene er også er isomorfe med disse. a0 b0. b2 b1. a3. a1. b3. b2. a3. a1. a0. a2. MAT1030 – Diskret matematikk. a2. b3. b1 b0. 14. april 2008. 7.
(46) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(47) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist.. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(48) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist. Hvis G og H er to grafer, så er en isomorfi mellom grafene en funksjon fra nodene i G til nodene i H som oppfyller bestemte egenskaper.. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(49) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist. Hvis G og H er to grafer, så er en isomorfi mellom grafene en funksjon fra nodene i G til nodene i H som oppfyller bestemte egenskaper.. Definisjon (Isomorfi). MAT1030 – Diskret matematikk. 14. april 2008. 8.
(50) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist. Hvis G og H er to grafer, så er en isomorfi mellom grafene en funksjon fra nodene i G til nodene i H som oppfyller bestemte egenskaper.. Definisjon (Isomorfi) La G og H være to enkle grafer slik at V (G ) er mengden av noder i G og V (H) er mengden av noder i H.. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(51) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist. Hvis G og H er to grafer, så er en isomorfi mellom grafene en funksjon fra nodene i G til nodene i H som oppfyller bestemte egenskaper.. Definisjon (Isomorfi) La G og H være to enkle grafer slik at V (G ) er mengden av noder i G og V (H) er mengden av noder i H. En isomorfi fra G til H er en funksjon f : V (G ) → V (H) med følgende egenskaper:. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(52) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist. Hvis G og H er to grafer, så er en isomorfi mellom grafene en funksjon fra nodene i G til nodene i H som oppfyller bestemte egenskaper.. Definisjon (Isomorfi) La G og H være to enkle grafer slik at V (G ) er mengden av noder i G og V (H) er mengden av noder i H. En isomorfi fra G til H er en funksjon f : V (G ) → V (H) med følgende egenskaper: f er surjektiv og injektiv. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(53) Grafisomorfier Vi skal nå gjøre isomorfibegrepet helt presist. Hvis G og H er to grafer, så er en isomorfi mellom grafene en funksjon fra nodene i G til nodene i H som oppfyller bestemte egenskaper.. Definisjon (Isomorfi) La G og H være to enkle grafer slik at V (G ) er mengden av noder i G og V (H) er mengden av noder i H. En isomorfi fra G til H er en funksjon f : V (G ) → V (H) med følgende egenskaper: f er surjektiv og injektiv Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H.. MAT1030 – Diskret matematikk. 14. april 2008. 8.
(54) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(55) Grafisomorfier. Eksempel. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(56) Grafisomorfier. Eksempel La grafen G bestå av nodene {a, b, c, d} og kantene {ab, bc, cd, da}.. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(57) Grafisomorfier. Eksempel La grafen G bestå av nodene {a, b, c, d} og kantene {ab, bc, cd, da}. La grafen H bestå av nodene {1, 2, 3, 4} og kantene {14, 34, 12, 32}.. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(58) Grafisomorfier. Eksempel La grafen G bestå av nodene {a, b, c, d} og kantene {ab, bc, cd, da}. La grafen H bestå av nodene {1, 2, 3, 4} og kantene {14, 34, 12, 32}. Funksjonen f slik at f (a) = 1, f (b) = 2, f (c) = 3 og f (d) = 4 er en isomorfi.. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(59) Grafisomorfier. Eksempel La grafen G bestå av nodene {a, b, c, d} og kantene {ab, bc, cd, da}. La grafen H bestå av nodene {1, 2, 3, 4} og kantene {14, 34, 12, 32}. Funksjonen f slik at f (a) = 1, f (b) = 2, f (c) = 3 og f (d) = 4 er en isomorfi. F.eks. ser vi at a og b er naboer i G (siden ab er en kant).. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(60) Grafisomorfier. Eksempel La grafen G bestå av nodene {a, b, c, d} og kantene {ab, bc, cd, da}. La grafen H bestå av nodene {1, 2, 3, 4} og kantene {14, 34, 12, 32}. Funksjonen f slik at f (a) = 1, f (b) = 2, f (c) = 3 og f (d) = 4 er en isomorfi. F.eks. ser vi at a og b er naboer i G (siden ab er en kant). Da må f (a) og f (b), som er 1 og 2, være naboer i H.. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(61) Grafisomorfier. Eksempel La grafen G bestå av nodene {a, b, c, d} og kantene {ab, bc, cd, da}. La grafen H bestå av nodene {1, 2, 3, 4} og kantene {14, 34, 12, 32}. Funksjonen f slik at f (a) = 1, f (b) = 2, f (c) = 3 og f (d) = 4 er en isomorfi. F.eks. ser vi at a og b er naboer i G (siden ab er en kant). Da må f (a) og f (b), som er 1 og 2, være naboer i H. Det stemmer, siden 12 er en kant i H.. MAT1030 – Diskret matematikk. 14. april 2008. 9.
(62) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 10.
(63) Grafisomorfier. c. b. 2. d. 3. a. MAT1030 – Diskret matematikk. 4. 1. 14. april 2008. 10.
(64) Grafisomorfier. c. b. 2. d. 3. a. MAT1030 – Diskret matematikk. 4. 1. 14. april 2008. 10.
(65) Grafisomorfier. c. b. 2. d. 3. a. MAT1030 – Diskret matematikk. 4. 1. 14. april 2008. 10.
(66) Grafisomorfier. c. b. 2. d. 3. a. MAT1030 – Diskret matematikk. 4. 1. 14. april 2008. 10.
(67) Grafisomorfier. c. b. 2. d. 3. a. MAT1030 – Diskret matematikk. 4. 1. 14. april 2008. 10.
(68) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(69) Grafisomorfier Merk. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(70) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen:. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(71) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H.. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(72) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden:. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(73) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H.. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(74) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H. Det betyr at hvis nodene u og v ikke er naboer, så er heller ikke nodene f (u) og f (v ) naboer.. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(75) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H. Det betyr at hvis nodene u og v ikke er naboer, så er heller ikke nodene f (u) og f (v ) naboer. “Naboer i H → Naboer i G ”. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(76) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H. Det betyr at hvis nodene u og v ikke er naboer, så er heller ikke nodene f (u) og f (v ) naboer. “Naboer i H → Naboer i G ”. Bare hvis-delen av definisjonen er denne påstanden:. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(77) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H. Det betyr at hvis nodene u og v ikke er naboer, så er heller ikke nodene f (u) og f (v ) naboer. “Naboer i H → Naboer i G ”. Bare hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer bare hvis nodene f (u) og f (v ) naboer.. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(78) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H. Det betyr at hvis nodene u og v ikke er naboer, så er heller ikke nodene f (u) og f (v ) naboer. “Naboer i H → Naboer i G ”. Bare hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer bare hvis nodene f (u) og f (v ) naboer. Det betyr at hvis nodene u og v er naboer, så er også nodene f (u) og f (v ) naboer.. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(79) Grafisomorfier Merk Det står “hvis og bare hvis” i definisjonen: Nodene u og v er naboer i G hvis og bare hvis nodene f (u) og f (v ) er naboer i H. Hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer i G hvis nodene f (u) og f (v ) er naboer i H. Det betyr at hvis nodene u og v ikke er naboer, så er heller ikke nodene f (u) og f (v ) naboer. “Naboer i H → Naboer i G ”. Bare hvis-delen av definisjonen er denne påstanden: Nodene u og v er naboer bare hvis nodene f (u) og f (v ) naboer. Det betyr at hvis nodene u og v er naboer, så er også nodene f (u) og f (v ) naboer. “Naboer i G → Naboer i H”. MAT1030 – Diskret matematikk. 14. april 2008. 11.
(80) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(81) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(82) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(83) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(84) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har. En grafteorisk egenskap er en egenskap som bevares under “lovlige” tranformasjoner, som å flytte rundt på nodene, gjøre kantene lengre/kortere, etc.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(85) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har. En grafteorisk egenskap er en egenskap som bevares under “lovlige” tranformasjoner, som å flytte rundt på nodene, gjøre kantene lengre/kortere, etc. Noen av de enkleste grafteoriske egenskapene er f.eks.:. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(86) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har. En grafteorisk egenskap er en egenskap som bevares under “lovlige” tranformasjoner, som å flytte rundt på nodene, gjøre kantene lengre/kortere, etc. Noen av de enkleste grafteoriske egenskapene er f.eks.: Hvor mange noder en graf har.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(87) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har. En grafteorisk egenskap er en egenskap som bevares under “lovlige” tranformasjoner, som å flytte rundt på nodene, gjøre kantene lengre/kortere, etc. Noen av de enkleste grafteoriske egenskapene er f.eks.: Hvor mange noder en graf har. Hvor mange kanter en graf har.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(88) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har. En grafteorisk egenskap er en egenskap som bevares under “lovlige” tranformasjoner, som å flytte rundt på nodene, gjøre kantene lengre/kortere, etc. Noen av de enkleste grafteoriske egenskapene er f.eks.: Hvor mange noder en graf har. Hvor mange kanter en graf har. Hvor mange noder av en bestemt grad en graf har.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(89) Grafisomorfier For å vise at to grafer er isomorfe, må man gi en funksjon og argumentere for at funksjonen har egenskapene som er nødvendige. Det fins per i dag ingen effektiv algoritme for å avgjøre om to grafer er isomorfe. For å vise at to grafer ikke er isomorfe, så er det tilstrekkelig å finne en “grafteorisk egenskap” som kun den ene av grafene har. En grafteorisk egenskap er en egenskap som bevares under “lovlige” tranformasjoner, som å flytte rundt på nodene, gjøre kantene lengre/kortere, etc. Noen av de enkleste grafteoriske egenskapene er f.eks.: Hvor mange noder en graf har. Hvor mange kanter en graf har. Hvor mange noder av en bestemt grad en graf har. Korteste avstand mellom to noder.. MAT1030 – Diskret matematikk. 14. april 2008. 12.
(90) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 13.
(91) Grafisomorfier Er følgende grafer isomorfe?. MAT1030 – Diskret matematikk. 14. april 2008. 13.
(92) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. MAT1030 – Diskret matematikk. d. 1. 14. april 2008. 13.
(93) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. MAT1030 – Diskret matematikk. d. 1. 14. april 2008. 13.
(94) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. MAT1030 – Diskret matematikk. d. 1. 14. april 2008. 13.
(95) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. MAT1030 – Diskret matematikk. d. 1. 14. april 2008. 13.
(96) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. MAT1030 – Diskret matematikk. d. ? 1. 14. april 2008. 13.
(97) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. d. ? 1. Nei, de er ikke isomorfe.. MAT1030 – Diskret matematikk. 14. april 2008. 13.
(98) Grafisomorfier Er følgende grafer isomorfe?. b. 2. c 3. a. d. ? 1. Nei, de er ikke isomorfe. Grafen til høyre har færre noder enn grafen til venstre, så ingen funksjon fra den venstre grafen til den høyre kan være injektiv eller en-til-en.. MAT1030 – Diskret matematikk. 14. april 2008. 13.
(99) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(100) Grafisomorfier Er følgende grafer isomorfe?. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(101) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 3. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(102) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 3. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(103) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 3. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(104) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 3. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(105) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 ? 3. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(106) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 ? 3 Nei, de er ikke isomorfe.. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(107) Grafisomorfier Er følgende grafer isomorfe? 2. a. b. d. c. 1 ? 3 Nei, de er ikke isomorfe. Grafen til høyre har flere noder enn grafen til venstre, så ingen funksjon fra den venstre grafen til den høyre kan være surjektiv eller på.. MAT1030 – Diskret matematikk. 14. april 2008. 14.
(108) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 15.
(109) Grafisomorfier Er følgende grafer, G og H, isomorfe?. MAT1030 – Diskret matematikk. 14. april 2008. 15.
(110) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. MAT1030 – Diskret matematikk. 14. april 2008. 1. 15.
(111) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. MAT1030 – Diskret matematikk. 14. april 2008. 1. 15.
(112) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. MAT1030 – Diskret matematikk. 14. april 2008. 1. 15.
(113) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. MAT1030 – Diskret matematikk. 14. april 2008. 1. 15.
(114) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. MAT1030 – Diskret matematikk. 14. april 2008. 1. 15.
(115) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. 1. Ja, de er isomorfe.. MAT1030 – Diskret matematikk. 14. april 2008. 15.
(116) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. 1. Ja, de er isomorfe. Funksjonen f : V (G ) → V (H) gitt ved f (a) = 1, f (b) = 2, f (c) = 3 og f (d) = 4 er en isomorfi.. MAT1030 – Diskret matematikk. 14. april 2008. 15.
(117) Grafisomorfier Er følgende grafer, G og H, isomorfe? 4 c. d. 3 a. b 2. 1. Ja, de er isomorfe. Funksjonen f : V (G ) → V (H) gitt ved f (a) = 1, f (b) = 2, f (c) = 3 og f (d) = 4 er en isomorfi. Vi ser at u og v er naboer i G hvis og bare hvis f (u) og f (v ) er naboer i H. MAT1030 – Diskret matematikk. 14. april 2008. 15.
(118) Grafisomorfier. MAT1030 – Diskret matematikk. 14. april 2008. 16.
(119) Grafisomorfier Er følgende grafer isomorfe?. MAT1030 – Diskret matematikk. 14. april 2008. 16.
(120) Grafisomorfier Er følgende grafer isomorfe?. Nei, de er ikke isomorfe.. MAT1030 – Diskret matematikk. 14. april 2008. 16.
(121) Grafisomorfier Er følgende grafer isomorfe?. Nei, de er ikke isomorfe. Grafen til venstre innholder tre noder som alle er relatert til hverandre; det gjør ikke grafen til høyre.. MAT1030 – Diskret matematikk. 14. april 2008. 16.
(122) Noen kommentarer. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(123) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med.. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(124) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med. Hvis en rekke grafer er gitt, så ønsker vi å finne ut om noen av dem er isomorfe for å unngå å gjøre overflødig arbeid.. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(125) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med. Hvis en rekke grafer er gitt, så ønsker vi å finne ut om noen av dem er isomorfe for å unngå å gjøre overflødig arbeid. Det er ingen som har klart å lage en effektiv algoritme (polynomiell tid) for å avgjøre om grafer er isomorfe (i det generelle tilfellet).. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(126) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med. Hvis en rekke grafer er gitt, så ønsker vi å finne ut om noen av dem er isomorfe for å unngå å gjøre overflødig arbeid. Det er ingen som har klart å lage en effektiv algoritme (polynomiell tid) for å avgjøre om grafer er isomorfe (i det generelle tilfellet). Mange spesialtilfeller, f.eks. trær, vet man mye om.. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(127) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med. Hvis en rekke grafer er gitt, så ønsker vi å finne ut om noen av dem er isomorfe for å unngå å gjøre overflødig arbeid. Det er ingen som har klart å lage en effektiv algoritme (polynomiell tid) for å avgjøre om grafer er isomorfe (i det generelle tilfellet). Mange spesialtilfeller, f.eks. trær, vet man mye om. I praksis så klarer man å lage ganske effektive algoritmer allikevel, men i verste tilfelle må man backtracke over alle n! mulige omdøpinger av nodene.. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(128) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med. Hvis en rekke grafer er gitt, så ønsker vi å finne ut om noen av dem er isomorfe for å unngå å gjøre overflødig arbeid. Det er ingen som har klart å lage en effektiv algoritme (polynomiell tid) for å avgjøre om grafer er isomorfe (i det generelle tilfellet). Mange spesialtilfeller, f.eks. trær, vet man mye om. I praksis så klarer man å lage ganske effektive algoritmer allikevel, men i verste tilfelle må man backtracke over alle n! mulige omdøpinger av nodene. Å finne isomorfier fra en graf til seg selv er en måte å avdekke symmetrier på.. MAT1030 – Diskret matematikk. 14. april 2008. 17.
(129) Noen kommentarer Å avgjøre om to grafer er isomorfe er i bunn og grunn å finne ut om det er den samme grafen man har å gjøre med. Hvis en rekke grafer er gitt, så ønsker vi å finne ut om noen av dem er isomorfe for å unngå å gjøre overflødig arbeid. Det er ingen som har klart å lage en effektiv algoritme (polynomiell tid) for å avgjøre om grafer er isomorfe (i det generelle tilfellet). Mange spesialtilfeller, f.eks. trær, vet man mye om. I praksis så klarer man å lage ganske effektive algoritmer allikevel, men i verste tilfelle må man backtracke over alle n! mulige omdøpinger av nodene. Å finne isomorfier fra en graf til seg selv er en måte å avdekke symmetrier på. Å finne ut om en graf er en delgraf av en annen er et annet, men relatert, problem. (Ofte vanskeligere.) MAT1030 – Diskret matematikk. 14. april 2008. 17.
(130) Stier og kretser. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(131) Stier og kretser. Vårt neste tema er stier (engelsk: path) og kretser (engelsk: circuit).. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(132) Stier og kretser. Vårt neste tema er stier (engelsk: path) og kretser (engelsk: circuit). Vi skal begynne med det klassiske eksemplet om Königsbergs broer.. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(133) Stier og kretser. Vårt neste tema er stier (engelsk: path) og kretser (engelsk: circuit). Vi skal begynne med det klassiske eksemplet om Königsbergs broer. Kort fortalt har vi sju broer som forbinder fire landområder.. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(134) Stier og kretser. Vårt neste tema er stier (engelsk: path) og kretser (engelsk: circuit). Vi skal begynne med det klassiske eksemplet om Königsbergs broer. Kort fortalt har vi sju broer som forbinder fire landområder. Spørsmålet er om det går an å gå en tur i Königsberg slik at man går over hver av de sju broene nøyaktig én gang.. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(135) Stier og kretser. Vårt neste tema er stier (engelsk: path) og kretser (engelsk: circuit). Vi skal begynne med det klassiske eksemplet om Königsbergs broer. Kort fortalt har vi sju broer som forbinder fire landområder. Spørsmålet er om det går an å gå en tur i Königsberg slik at man går over hver av de sju broene nøyaktig én gang. Dette er kjent for å ha blitt løst av Leonhard Euler omkring 1735.. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(136) Stier og kretser. Vårt neste tema er stier (engelsk: path) og kretser (engelsk: circuit). Vi skal begynne med det klassiske eksemplet om Königsbergs broer. Kort fortalt har vi sju broer som forbinder fire landområder. Spørsmålet er om det går an å gå en tur i Königsberg slik at man går over hver av de sju broene nøyaktig én gang. Dette er kjent for å ha blitt løst av Leonhard Euler omkring 1735. Vi skal se at oppgaven er den samme som å finne en Eulersti i grafen som representer Königsberg.. MAT1030 – Diskret matematikk. 14. april 2008. 18.
(137) Königsbergs broer. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(138) Königsbergs broer. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(139) Königsbergs broer. Vi representerer situasjonen med en graf. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(140) Königsbergs broer. C. B. D. A. Vi representerer situasjonen med en graf. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(141) Königsbergs broer. C. B. D. A. Vi representerer situasjonen med en graf. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(142) Königsbergs broer. C. B. D. A. Vi representerer situasjonen med en graf. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(143) Königsbergs broer. C. B. D. A. Vi representerer situasjonen med en graf. Spørsmålet blir nå om det er mulig å gå over alle kantene nøyaktig en gang. MAT1030 – Diskret matematikk. 14. april 2008. 19.
(144) Stier og kretser. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(145) Stier og kretser Definisjon (Sti). MAT1030 – Diskret matematikk. 14. april 2008. 20.
(146) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(147) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(148) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(149) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(150) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn .. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(151) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn . En sti kalles også for en vei.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(152) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn . En sti kalles også for en vei. Lengden til en sti er det samme som antall kanter i stien.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(153) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn . En sti kalles også for en vei. Lengden til en sti er det samme som antall kanter i stien. En enkelt node er både en sti og en krets av lengde 0.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(154) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn . En sti kalles også for en vei. Lengden til en sti er det samme som antall kanter i stien. En enkelt node er både en sti og en krets av lengde 0. Hvis grafen er enkel, tillater vi oss å skrive v0 v1 v2 . . . vn for stien.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(155) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn . En sti kalles også for en vei. Lengden til en sti er det samme som antall kanter i stien. En enkelt node er både en sti og en krets av lengde 0. Hvis grafen er enkel, tillater vi oss å skrive v0 v1 v2 . . . vn for stien. Vær oppmerksom på at terminologien for grafteori varierer fra lærebok til lærebok.. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(156) Stier og kretser Definisjon (Sti) En sti av lengde n i en graf er sekvens av noder og kanter på formen v0 e1 v1 e2 v2 . . . en vn hvor ei er en kant som forbinder vi−1 og vi for i ∈ {1, 2, . . . , n}. En sti hvor v0 = vn kalles en krets. Vi sier at sekvensen er en sti fra v0 til vn . En sti kalles også for en vei. Lengden til en sti er det samme som antall kanter i stien. En enkelt node er både en sti og en krets av lengde 0. Hvis grafen er enkel, tillater vi oss å skrive v0 v1 v2 . . . vn for stien. Vær oppmerksom på at terminologien for grafteori varierer fra lærebok til lærebok. Vi ser på noen eksempler. MAT1030 – Diskret matematikk. 14. april 2008. 20.
(157) Stier og kretser. a. 1. 5. 3. c. 4. e. d. f. MAT1030 – Diskret matematikk. b. 2. h g. 6. 14. april 2008. 21.
(158) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(159) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1a2. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(160) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1a2d5. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(161) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1a2d5g 6. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(162) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1a2d5g 6e3. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(163) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1a2d5g 6e3c4. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(164) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1a2d5g 6e3c4 er en sti fra 1 til 4.. MAT1030 – Diskret matematikk. 14. april 2008. 21.
(165) Stier og kretser. a. 1. 5. 3. c. 4. e. d. f. MAT1030 – Diskret matematikk. b. 2. h g. 6. 14. april 2008. 22.
(166) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(167) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(168) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(169) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6e3. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(170) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6e3b2. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(171) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6e3b2d5. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(172) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6e3b2d5g 6. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(173) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6e3b2d5g 6h4. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(174) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 1f 5g 6e3b2d5g 6h4 er en sti fra 1 til 4.. MAT1030 – Diskret matematikk. 14. april 2008. 22.
(175) Stier og kretser. a. 1. 5. 3. c. 4. e. d. f. MAT1030 – Diskret matematikk. b. 2. h g. 6. 14. april 2008. 23.
(176) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 5. MAT1030 – Diskret matematikk. 14. april 2008. 23.
(177) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 5g 6. MAT1030 – Diskret matematikk. 14. april 2008. 23.
(178) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 5g 6e3. MAT1030 – Diskret matematikk. 14. april 2008. 23.
(179) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 5g 6e3b2. MAT1030 – Diskret matematikk. 14. april 2008. 23.
(180) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 5g 6e3b2d5. MAT1030 – Diskret matematikk. 14. april 2008. 23.
(181) Stier og kretser. a. 1. b. 2. 5. c. 4. e. d. f. 3. h g. 6. 5g 6e3b2d5 er en krets som begynner og slutter i 5.. MAT1030 – Diskret matematikk. 14. april 2008. 23.
(182) Stier og kretser. MAT1030 – Diskret matematikk. 14. april 2008. 24.
(183) Stier og kretser Hvis en graf er enkel fins det ingen parallelle kanter, og da kan vi betegne en sti som en sekvens av noder.. MAT1030 – Diskret matematikk. 14. april 2008. 24.
(184) Stier og kretser Hvis en graf er enkel fins det ingen parallelle kanter, og da kan vi betegne en sti som en sekvens av noder. Det er vanlig å identifisere kretser som kun er forskjellige med hensyn på startnode eller rekkefølge.. MAT1030 – Diskret matematikk. 14. april 2008. 24.
(185) Stier og kretser Hvis en graf er enkel fins det ingen parallelle kanter, og da kan vi betegne en sti som en sekvens av noder. Det er vanlig å identifisere kretser som kun er forskjellige med hensyn på startnode eller rekkefølge.. MAT1030 – Diskret matematikk. 2. 3. 1. 4. 14. april 2008. 24.
(186) Stier og kretser Hvis en graf er enkel fins det ingen parallelle kanter, og da kan vi betegne en sti som en sekvens av noder. Det er vanlig å identifisere kretser som kun er forskjellige med hensyn på startnode eller rekkefølge. 2. 3. 1. 4. Her er 12341 en krets.. MAT1030 – Diskret matematikk. 14. april 2008. 24.
(187) Stier og kretser Hvis en graf er enkel fins det ingen parallelle kanter, og da kan vi betegne en sti som en sekvens av noder. Det er vanlig å identifisere kretser som kun er forskjellige med hensyn på startnode eller rekkefølge. 2. 3. 1. 4. Her er 12341 en krets. Vi identifiserer denne med kretsene 23412, 34123, etc., og 43214, 32143, etc.. MAT1030 – Diskret matematikk. 14. april 2008. 24.
(188) Stier og kretser. MAT1030 – Diskret matematikk. 14. april 2008. 25.
(189) Stier og kretser. Oppgave. MAT1030 – Diskret matematikk. 14. april 2008. 25.
(190) Stier og kretser. Oppgave Hvor mange forskjellige kretser som inneholder alle kantene nøyaktig én gang fins i følgende graf?. MAT1030 – Diskret matematikk. 14. april 2008. 25.
(191) Stier og kretser. Oppgave Hvor mange forskjellige kretser som inneholder alle kantene nøyaktig én gang fins i følgende graf? 2. 3 1. 4. MAT1030 – Diskret matematikk. 5. 14. april 2008. 25.
(192) Stier og kretser. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(193) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(194) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt). MAT1030 – Diskret matematikk. 14. april 2008. 26.
(195) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt) En sekvens som består av en node v er en sti.. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(196) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt) En sekvens som består av en node v er en sti. Hvis p er en sti, og det siste elementet i p er noden u. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(197) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt) En sekvens som består av en node v er en sti. Hvis p er en sti, og det siste elementet i p er noden u, og det går en kant fra u til v. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(198) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt) En sekvens som består av en node v er en sti. Hvis p er en sti, og det siste elementet i p er noden u, og det går en kant fra u til v , så er sekvensen pev en sti.. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(199) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt) En sekvens som består av en node v er en sti. Hvis p er en sti, og det siste elementet i p er noden u, og det går en kant fra u til v , så er sekvensen pev en sti. Mengden av stier er den minste mengden som oppfyller disse to kravene.. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(200) Stier og kretser Vi kan definere mengder av stier induktivt på følgende måte.. Definisjon (Mengden av stier - induktivt) En sekvens som består av en node v er en sti. Hvis p er en sti, og det siste elementet i p er noden u, og det går en kant fra u til v , så er sekvensen pev en sti. Mengden av stier er den minste mengden som oppfyller disse to kravene. Når vi nå har begrepet om en sti kan vi definere sammenhengende grafer mer presist.. MAT1030 – Diskret matematikk. 14. april 2008. 26.
(201)
RELATERTE DOKUMENTER
Hvis den første hatten er svart, s˚a m˚a tre av de fire resterende hattene være oransje.. Det er
Det finnes en bijeksjon mellom nodene og mellom kantene slik at bildet av en kant g˚ ar mellom bildet av to noder hvis og bare hvis kanten g˚ ar mellom nodene.. Vi definerte stier
Det finnes en bijeksjon mellom nodene og mellom kantene slik at bildet av en kant g˚ ar mellom bildet av to noder hvis og bare hvis kanten g˚ ar mellom nodene.. Vi definerte stier
c) Finnes det to sammenhengende grafer med fem noder og minimalt med kanter som ikke er isomorfe, slik at begge har en Eulersti? Begrunn svaret... Grafer og
c) Finnes det to sammenhengende grafer med fem noder og minimalt med kanter som ikke er isomorfe, slik at begge har en Eulersti?. Begrunn svaret... mai
c) Finnes det to sammenhengende grafer med fem noder og minimalt med kanter som ikke er isomorfe, slik at begge har en Eulersti?. Begrunn
En kontrollstruktur brukes for ˚ a styre hvordan, og hvorvidt, de enkle instruksjonene i en pseudokode skal
ikkesiffer oppdaget kalles gjerne for en logisk (eller Boolsk) variabel, siden den kun vil ta verdiene true eller false.. Kunne ha skrevet ‘until ikkesiffer oppdaget ’ i
