Virtaukset ja niiden sovelluksia

Tässä tutkielmassa perehdytään verkostoihin ja niihin määriteltyihin virtauksiin. Virtaus on funktio, joka liittää jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon ja toteuttaa tietyt ehdot. Ensinnäkin, jokaiselle suunnatulle sivulle tulee päteä, että vastakkaiselle suunnatulle sivulle virta...

Full description

Bibliographic Details
Main Author: Leirimaa, Elisa
Other Authors: Matemaattis-luonnontieteellinen tiedekunta, Faculty of Sciences, Matematiikan ja tilastotieteen laitos, Department of Mathematics and Statistics, Jyväskylän yliopisto, University of Jyväskylä
Format: Master's thesis
Language:fin
Published: 2020
Subjects:
Online Access: https://jyx.jyu.fi/handle/123456789/69350
_version_ 1826225730368831488
author Leirimaa, Elisa
author2 Matemaattis-luonnontieteellinen tiedekunta Faculty of Sciences Matematiikan ja tilastotieteen laitos Department of Mathematics and Statistics Jyväskylän yliopisto University of Jyväskylä
author_facet Leirimaa, Elisa Matemaattis-luonnontieteellinen tiedekunta Faculty of Sciences Matematiikan ja tilastotieteen laitos Department of Mathematics and Statistics Jyväskylän yliopisto University of Jyväskylä Leirimaa, Elisa Matemaattis-luonnontieteellinen tiedekunta Faculty of Sciences Matematiikan ja tilastotieteen laitos Department of Mathematics and Statistics Jyväskylän yliopisto University of Jyväskylä
author_sort Leirimaa, Elisa
datasource_str_mv jyx
description Tässä tutkielmassa perehdytään verkostoihin ja niihin määriteltyihin virtauksiin. Virtaus on funktio, joka liittää jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon ja toteuttaa tietyt ehdot. Ensinnäkin, jokaiselle suunnatulle sivulle tulee päteä, että vastakkaiselle suunnatulle sivulle virtauksen arvo on yhtä suuri mutta eri merkkinen. Toiseksi jokaisesta kärjestä lähde ja nielu poislukien on lähdettävä virtausta yhtä paljon kuin siihen on saapunut. Lähde on se kärki, josta virtaus lähtee liikkeelle, ja nielu on kärki, johon virtaus lopulta päätyy. Kolmanneksi virtauksen arvon on oltava jokaisessa suunnatussa sivussa korkeintaan yhtä suuri kuin vastaava kapasiteettifunktion arvo. Kapasiteettifunktio liittää jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon, joka kuvaa kunkin suunnatun sivun suurinta mahdollista virtauksen arvoa. Tutkielmassa osoitetaan lause, joka kertoo, että verkoston läpi kulkevan suurimman mahdollisen virtauksen arvo on sama kuin pienimmän leikkauksen kapasiteetin arvo. Tätä Fordin ja Fulkersonin kehittämää lausetta kutsutaan suurin virtaus - pienin leikkaus -lauseeksi. Tätä lausetta hyödynnetään läpi koko tutkielman, ja sen avulla osoitetaan keskeisiä verkkoteorian tuloksia, kuten Königin lause, Hallin lause ja Mengerin lause. Königin lauseen mukaan verkon maksimaalisen sovituksen suuruus on sama kuin pienimmän peitteen suuruus. Hallin lause antaa välttämättömän ja toisaalta riittävän ehdon sille, että kaksiosaiselle verkolle löytyy täydellinen sovitus. Mengerin lause puolestaan antaa verkoston suurimman mahdollisen lukumäärän erillisiä polkuja. Nämä tulokset saadaan osoitettua konstruoimalla verkosta verkosto ja lähettämällä virtausta lähteestä verkoston läpi. Näin voidaan hyödyntää virtauksille ja verkostoille osoitettuja tuloksia.
first_indexed 2024-09-11T08:52:40Z
format Pro gradu
free_online_boolean 1
fullrecord [{"key": "dc.contributor.advisor", "value": "V\u00e4h\u00e4kangas, Antti", "language": "", "element": "contributor", "qualifier": "advisor", "schema": "dc"}, {"key": "dc.contributor.author", "value": "Leirimaa, Elisa", "language": "", "element": "contributor", "qualifier": "author", "schema": "dc"}, {"key": "dc.date.accessioned", "value": "2020-06-01T12:27:21Z", "language": null, "element": "date", "qualifier": "accessioned", "schema": "dc"}, {"key": "dc.date.available", "value": "2020-06-01T12:27:21Z", "language": null, "element": "date", "qualifier": "available", "schema": "dc"}, {"key": "dc.date.issued", "value": "2020", "language": "", "element": "date", "qualifier": "issued", "schema": "dc"}, {"key": "dc.identifier.uri", "value": "https://jyx.jyu.fi/handle/123456789/69350", "language": null, "element": "identifier", "qualifier": "uri", "schema": "dc"}, {"key": "dc.description.abstract", "value": "T\u00e4ss\u00e4 tutkielmassa perehdyt\u00e4\u00e4n verkostoihin ja niihin m\u00e4\u00e4riteltyihin virtauksiin. Virtaus on funktio, joka liitt\u00e4\u00e4 jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon ja toteuttaa tietyt ehdot. Ensinn\u00e4kin, jokaiselle suunnatulle sivulle tulee p\u00e4te\u00e4, ett\u00e4 vastakkaiselle suunnatulle sivulle virtauksen arvo on yht\u00e4 suuri mutta eri merkkinen. Toiseksi jokaisesta k\u00e4rjest\u00e4 l\u00e4hde ja nielu poislukien on l\u00e4hdett\u00e4v\u00e4 virtausta yht\u00e4 paljon kuin siihen on saapunut. L\u00e4hde on se k\u00e4rki, josta virtaus l\u00e4htee liikkeelle, ja nielu on k\u00e4rki, johon virtaus lopulta p\u00e4\u00e4tyy. Kolmanneksi virtauksen arvon on oltava jokaisessa suunnatussa sivussa korkeintaan yht\u00e4 suuri kuin vastaava kapasiteettifunktion arvo. Kapasiteettifunktio liitt\u00e4\u00e4 jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon, joka kuvaa kunkin suunnatun sivun suurinta mahdollista virtauksen arvoa. Tutkielmassa osoitetaan lause, joka kertoo, ett\u00e4 verkoston l\u00e4pi kulkevan suurimman mahdollisen virtauksen arvo on sama kuin pienimm\u00e4n leikkauksen kapasiteetin arvo. T\u00e4t\u00e4 Fordin ja Fulkersonin kehitt\u00e4m\u00e4\u00e4 lausetta kutsutaan suurin virtaus - pienin leikkaus -lauseeksi. T\u00e4t\u00e4 lausetta hy\u00f6dynnet\u00e4\u00e4n l\u00e4pi koko tutkielman, ja sen avulla osoitetaan keskeisi\u00e4 verkkoteorian tuloksia, kuten K\u00f6nigin lause, Hallin lause ja Mengerin lause. K\u00f6nigin lauseen mukaan verkon maksimaalisen sovituksen suuruus on sama kuin pienimm\u00e4n peitteen suuruus. Hallin lause antaa v\u00e4ltt\u00e4m\u00e4tt\u00f6m\u00e4n ja toisaalta riitt\u00e4v\u00e4n ehdon sille, ett\u00e4 kaksiosaiselle verkolle l\u00f6ytyy t\u00e4ydellinen sovitus. Mengerin lause puolestaan antaa verkoston suurimman mahdollisen lukum\u00e4\u00e4r\u00e4n erillisi\u00e4 polkuja. N\u00e4m\u00e4 tulokset saadaan osoitettua konstruoimalla verkosta verkosto ja l\u00e4hett\u00e4m\u00e4ll\u00e4 virtausta l\u00e4hteest\u00e4 verkoston l\u00e4pi. N\u00e4in voidaan hy\u00f6dynt\u00e4\u00e4 virtauksille ja verkostoille osoitettuja tuloksia.", "language": "fi", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted by Paivi Vuorio (paelvuor@jyu.fi) on 2020-06-01T12:27:21Z\nNo. of bitstreams: 0", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Made available in DSpace on 2020-06-01T12:27:21Z (GMT). No. of bitstreams: 0\n Previous issue date: 2020", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.format.extent", "value": "41", "language": "", "element": "format", "qualifier": "extent", "schema": "dc"}, {"key": "dc.format.mimetype", "value": "application/pdf", "language": null, "element": "format", "qualifier": "mimetype", "schema": "dc"}, {"key": "dc.language.iso", "value": "fin", "language": null, "element": "language", "qualifier": "iso", "schema": "dc"}, {"key": "dc.rights", "value": "In Copyright", "language": "en", "element": "rights", "qualifier": null, "schema": "dc"}, {"key": "dc.subject.other", "value": "l\u00e4hde", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.title", "value": "Virtaukset ja niiden sovelluksia", "language": "", "element": "title", "qualifier": null, "schema": "dc"}, {"key": "dc.type", "value": "master thesis", "language": null, "element": "type", "qualifier": null, "schema": "dc"}, {"key": "dc.identifier.urn", "value": "URN:NBN:fi:jyu-202006013607", "language": "", "element": "identifier", "qualifier": "urn", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Pro gradu -tutkielma", "language": "fi", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Master\u2019s thesis", "language": "en", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Matemaattis-luonnontieteellinen tiedekunta", "language": "fi", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Faculty of Sciences", "language": "en", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Matematiikan ja tilastotieteen laitos", "language": "fi", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Department of Mathematics and Statistics", "language": "en", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "Jyv\u00e4skyl\u00e4n yliopisto", "language": "fi", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "University of Jyv\u00e4skyl\u00e4", "language": "en", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Matematiikan opettajankoulutus", "language": "fi", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Teacher education programme in Mathematics", "language": "en", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "yvv.contractresearch.funding", "value": "0", "language": "", "element": "contractresearch", "qualifier": "funding", "schema": "yvv"}, {"key": "dc.type.coar", "value": "http://purl.org/coar/resource_type/c_bdcc", "language": null, "element": "type", "qualifier": "coar", "schema": "dc"}, {"key": "dc.rights.accesslevel", "value": "openAccess", "language": null, "element": "rights", "qualifier": "accesslevel", "schema": "dc"}, {"key": "dc.type.publication", "value": "masterThesis", "language": null, "element": "type", "qualifier": "publication", "schema": "dc"}, {"key": "dc.subject.oppiainekoodi", "value": "4041", "language": "", "element": "subject", "qualifier": "oppiainekoodi", "schema": "dc"}, {"key": "dc.subject.yso", "value": "verkkoteoria", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "virtaus", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "verkostot", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "sovitukset", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "nielu", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.format.content", "value": "fulltext", "language": null, "element": "format", "qualifier": "content", "schema": "dc"}, {"key": "dc.rights.url", "value": "https://rightsstatements.org/page/InC/1.0/", "language": null, "element": "rights", "qualifier": "url", "schema": "dc"}, {"key": "dc.type.okm", "value": "G2", "language": null, "element": "type", "qualifier": "okm", "schema": "dc"}]
id jyx.123456789_69350
language fin
last_indexed 2025-02-18T10:56:51Z
main_date 2020-01-01T00:00:00Z
main_date_str 2020
online_boolean 1
online_urls_str_mv {"url":"https:\/\/jyx.jyu.fi\/bitstreams\/1ee76de7-4afa-4a0b-9fca-f7daa317c358\/download","text":"URN:NBN:fi:jyu-202006013607.pdf","source":"jyx","mediaType":"application\/pdf"}
publishDate 2020
record_format qdc
source_str_mv jyx
spellingShingle Leirimaa, Elisa Virtaukset ja niiden sovelluksia lähde Matematiikan opettajankoulutus Teacher education programme in Mathematics 4041 verkkoteoria virtaus verkostot sovitukset nielu
title Virtaukset ja niiden sovelluksia
title_full Virtaukset ja niiden sovelluksia
title_fullStr Virtaukset ja niiden sovelluksia Virtaukset ja niiden sovelluksia
title_full_unstemmed Virtaukset ja niiden sovelluksia Virtaukset ja niiden sovelluksia
title_short Virtaukset ja niiden sovelluksia
title_sort virtaukset ja niiden sovelluksia
title_txtP Virtaukset ja niiden sovelluksia
topic lähde Matematiikan opettajankoulutus Teacher education programme in Mathematics 4041 verkkoteoria virtaus verkostot sovitukset nielu
topic_facet 4041 Matematiikan opettajankoulutus Teacher education programme in Mathematics lähde nielu sovitukset verkkoteoria verkostot virtaus
url https://jyx.jyu.fi/handle/123456789/69350 http://www.urn.fi/URN:NBN:fi:jyu-202006013607
work_keys_str_mv AT leirimaaelisa virtauksetjaniidensovelluksia