Grafų teorija Turinys Istorija | Specialūs grafų atvejai | Uždaviniai bei problemos | Literatūra internete | Naršymo meniuK. Matuliauskas - Grafų teorijar
Grafų teorija
matematikosgrafusseptynis Karaliaučiaus tiltusK. Matuliauskas - Grafų teorija
(function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003Epaslėptiu003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="lt" dir="ltr"u003Eu003Cdiv class="floatleft"u003Eu003Ca href="/wiki/Vaizdas:Logo_CEE-t.png" class="image"u003Eu003Cimg alt="Logo CEE-t.png" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Logo_CEE-t.png/70px-Logo_CEE-t.png" decoding="async" width="70" height="45" data-file-width="548" data-file-height="356" /u003Eu003C/au003Eu003C/divu003Enu003Cpu003EŠios u003Ca href="/wiki/Vikipedija:Savait%C4%97s_iniciatyva" title="Vikipedija:Savaitės iniciatyva"u003Esavaitės iniciatyvau003C/au003E: u003Cbu003Egatvės maistasu003C/bu003E. Kviečiame prisidėti!u003Cbr /u003Eu003Cbr /u003EnKviečiame dalyvauti konkurse u003Cbu003Eu003Ca href="/wiki/Vikiprojektas:VRE_2019" title="Vikiprojektas:VRE 2019"u003EVidurio ir Rytų Europos „pavasaris“ 2019u003C/au003Eu003C/bu003E.nu003C/pu003Eu003C/divu003Eu003C/divu003Eu003C/divu003E";());
Grafų teorija
Jump to navigation
Jump to search
Grafų teorija – matematikos sritis, nagrinėjanti grafus. Grafas yra sudarytas iš lankais (briaunomis) sujungtų viršūnių.
Bekryptis grafas
Jei grafo briaunos turi kryptį, tai orientuotas grafas. Jei grafas turi tik vieną viršūnę ir nei vienos briaunos, tai trivialus grafas. Grafas be briaunų – tuščias grafas, o be viršūnių ir be briaunų – nulinis grafas.
Turinys
1 Istorija
2 Specialūs grafų atvejai
3 Uždaviniai bei problemos
4 Literatūra internete
Istorija |
L. Oilerio straipsnis apie septynis Karaliaučiaus tiltus laikomas pirmuoju grafų teorijos straipsniu.
Specialūs grafų atvejai |
Yra kelios rūšys specifinių grafų, pasižyminčių savitomis savybėmis:
Pilnasis grafas – grafas, kurio kiekviena viršūnė sujungta su kiekviena kita.
Medis – grafas, tarp kurio bet kurių dviejų viršūnių egzistuoja lygiai vienas kelias.
Plokščiasis grafas – grafą, kurį plokštumoje galima pavaizduoti taip, kad briaunos nesikirstų.
Uždaviniai bei problemos |
Populiariausi uždaviniai bei problemos, sprendžiamos grafų teorijos:
- Grafo nuspalvinimo uždavinys
- Kelio paieška:
- Septyni Karaliaučiaus tiltai
- Keliaujančio pirklio uždavinys
- Mažiausias aprėpiantis medis
- Steinerio medis
- Trumpiausio kelio problema
- Grafų panašumo uždaviniai
Literatūra internete |
K. Matuliauskas - Grafų teorija
| |||||||||||||||||||||||
Vikiteka
Kategorija:
- Grafų teorija
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.060","walltime":"0.077","ppvisitednodes":"value":542,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":19145,"limit":2097152,"templateargumentsize":"value":5201,"limit":2097152,"expansiondepth":"value":13,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":0,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 35.371 1 -total"," 91.61% 32.405 1 Šablonas:Informatika"," 83.24% 29.443 1 Šablonas:Navbox"," 25.78% 9.120 1 Šablonas:Navbar"," 11.70% 4.137 3 Šablonas:Transclude"," 8.10% 2.865 1 Šablonas:Commons"],"cachereport":"origin":"mw1248","timestamp":"20190413175452","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"Grafu0173 teorija","url":"https://lt.wikipedia.org/wiki/Graf%C5%B3_teorija","sameAs":"http://www.wikidata.org/entity/Q131476","mainEntity":"http://www.wikidata.org/entity/Q131476","author":"@type":"Organization","name":"Contributors to Wikimedia projects","publisher":"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2004-11-05T10:25:34Z","dateModified":"2015-03-07T20:07:49Z","image":"https://upload.wikimedia.org/wikipedia/commons/b/b8/BekryptisGrafas.png"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":126,"wgHostname":"mw1270"););
