Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Grafteori och algoritmer - Hamiltongrafer
2003 (Swedish)Independent thesis Basic level (degree of Bachelor)Student thesis
Abstract [sv]

Grafteori är en intressant och spännande gren av matematiken som många människor vet inte mycket om. Även om vi vet teorins ”födelsedag” och ”födelseplats”, problemet med de sju broarna i staden Köningsberg som löstes av L. Euler 1736, så var den nästan glömt i många årtionden. Dagens revolutionerande dataåldern har gjort den intressant igen, och idag ser vi många tillämpningar av den teori som utvecklades och utvecklas fortfarande när det gäller grafer och deras egenskaper. Tillämpningsområdena är många, såsom kodningsteori, elektriska nätverk, kemi, dataprogrammering, ”operations research” etc, etc. Första delen av denna uppsats ger en introduktion till grunderna i den ”klassiska” grafteorin utan att gå in på mer avancerad teori som utvecklades senare. Huvudpunkten ligger på den teori som utvecklades av den irländske matematikern R. W. Hamilton i mitten av 18 hundra talet. Det är intressant, men inte alltid lätt, att veta vilka grafer som är Hamiltongarfer. Vi har beskrivit några tillräckliga villkor eller egenskaper som en graf måste uppfylla för att vara Hamiltongraf, även om man inte känner till något enkelt nödvändigt och tillräckligt villkor för existens av Hamiltoncykler i en graf. Andra delen av uppsatsen handlar om hur man hittar en Hamiltoncykel i enkla grafer, samt hur kan man använda denna teori i praktiken för att lösa problem som t.ex. den kända handelsresandesproblem. Detta problem är fortfarande olöst i den mening att det inte finns någon känd algoritm (metod) som garanterat löser detta problem inom en tid som kan uttryckas som ett polynom av grafens komplexivitet. Vi har beskrivit en algoritm som är framgångsrik för grafer med få noder och som använder grafens kopplingsmatriser på väg till den optimala lösningen, som i sin tur är en av många Hamiltoncykler som grafen innehar.

Place, publisher, year, edition, pages
2003. , 32 p.
Identifiers
URN: urn:nbn:se:kau:diva-54773Local ID: MAT C-5OAI: oai:DiVA.org:kau-54773DiVA: diva2:1104537
Subject / course
Mathematics
Available from: 2017-06-01 Created: 2017-06-01

Open Access in DiVA

No full text

Search outside of DiVA

GoogleGoogle Scholar

Total: 3 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf