Skip to main content

Grafų teorija Turinys Istorija | Specialūs grafų atvejai | Uždaviniai bei problemos | Literatūra internete | Naršymo meniuK. Matuliauskas - Grafų teorijar

Multi tool use
Multi tool use

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




Straipsnis iš Vikipedijos, laisvosios enciklopedijos.






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


















ž • a • r
Informatikos sritys
Matematinė bazė

Būlio (logikos) algebra • Diskrečioji matematika • Grafų teorija • Informacijos teorija • Tikimybių teorija • Statistika
Teorinė informatika

Algoritminė informacijos teorija • Tiuringo mašina • Kriptografija • Algoritmų bei jų sudėtingumo tyrimai • Matematinė logika • Formalios kalbos • Tipų teorija • Rikiavimo algoritmų sudėtingumas
Taikomoji informatika

Bioinformatika • Geoinformatika • Ekonominė informatika • Neuroinformatika
Programinė įranga

Lygiagretusis programavimas • Programų specifikavimas • Programų patikrinimas • Programavimo technika • Programavimo kalbos • Operacinės sistemos • Kompiliatoriai (leksinė analizė)
Programų inžinerija

Optimizavimas • Programų metrikos • Konfigūracijų valdymas • Funkcinis programavimas • Struktūrinis programavimas • Objektinis programų kūrimas • Komponentinis programavimas • Šablonai • Atviras kodas
Duomenų ir informacijos sistemos

Duomenų struktūros • Duomenų vaizdavimas • Duomenų suspaudimas • Bylos • Bylų formatai • Informacinės sistemos • Duomenų bazės • Informacijos saugojimas
Skaičiavimo metodologijos

Dirbtinis intelektas • Kompiuterinė grafika • Vaizdų apdorojimas • Balso atpažinimas • Modeliavimas • Dokumentų ir teksto apdorojimas • Skaitmeninių signalų apdorojimas

Vikiteka









Rodomas puslapis "https://lt.wikipedia.org/w/index.php?title=Grafų_teorija&oldid=4724293"










Naršymo meniu


























(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"););905T7i zCaDx5Oi
-
wawF,OqrWbJfEE2 dfWb I,grAb7n9Vf Iwcrv2UYysz ksW8H4 dvPwRbkoq4Zy8DGK5,IsRwblHzd p4Oj0Pl4yY6pU6G

Popular posts from this blog

Aidahas Turinys Geografija | Klimatas | Istorija | Demografija | Religija | Ekonomika | Galerija | Naršymo meniuidaho.gov

Image
JAV valstijos angl.JAV1890liepos 3Boisėangl.VašingtonoOregonoNevadosJutosMontanosVajomingoBritų KolumbijaUoliniuose kalnuoseGyvačių upėHelso kanijonąangl.Skaidriavandenė upėangl.Lašišų upėangl.Boraho viršūnėLevistonasangl.Ramusis vandenynasAnglijaibulvių (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=...
Read more

Creating centerline of river in QGIS? The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Finding centrelines from polygons in QGIS?Splitting line into two lines with GRASS GIS?Centroid of the equator and a pointpostgis: problems creating flow direction polyline; not all needed connections are drawnhow to make decent sense from scattered river depth measurementsQGIS Interpolation on Curved Grid (River DEMs)How to create automatic parking baysShortest path creation between two linesclipping layer using query builder in QGISFinding which side of closest polyline point lies on in QGIS?Create centerline from multi-digitized roadway lines Qgis 2.18Getting bathymetric contours confined only within river banks using QGIS?

Image
Calculating the number of coins in money change How could chocolate be as addictive as heroin? What do you call a plan that's an alternative plan in case your initial plan fails? Python - Fishing Simulator Simulating Exploding Dice Active filter with series inductor and resistor - do these exist? How can I protect witches in combat who wear limited clothing? Am I ethically obligated to go into work on an off day if the reason is sudden? Format single node in tikzcd Didn't get enough time to take a Coding Test - what to do now? Why can't wing-mounted spoilers be used to steepen approaches? How is simplicity better than precision and clarity in prose? Is there a trick to getting spices to fix to nuts? What can I do if neighbor is blocking my solar panels intentionally? Hiding Certain Lines on Table Wolves and sheep Make it rain characters Can the prologue be the backstory of your main character? Difference between はじめる and ...
Read more

Typsetting diagram chases (with TikZ?) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to define the default vertical distance between nodes?Draw edge on arcNumerical conditional within tikz keys?TikZ: Drawing an arc from an intersection to an intersectionDrawing rectilinear curves in Tikz, aka an Etch-a-Sketch drawingLine up nested tikz enviroments or how to get rid of themHow to place nodes in an absolute coordinate system in tikzCommutative diagram with curve connecting between nodesTikz with standalone: pinning tikz coordinates to page cmDrawing a Decision Diagram with Tikz and layout manager

Image
What LEGO pieces have "real-world" functionality? Why does tar appear to skip file contents when output file is /dev/null? Passing functions in C++ What computer would be fastest for Mathematica Home Edition? Active filter with series inductor and resistor - do these exist? How do you clear the ApexPages.getMessages() collection in a test? Strange behaviour of Check Is it possible to ask for a hotel room without minibar/extra services? Is 1 ppb equal to 1 μg/kg? The following signatures were invalid: EXPKEYSIG 1397BC53640DB551 Stopping real property loss from eroding embankment If I can make up priors, why can't I make up posteriors? What are the performance impacts of 'functional' Rust? Is above average number of years spent on PhD considered a red flag in future academia or industry positions? When is phishing education going too far? Need a suitable toxic chemical for a murder plot in my novel How do I automatically answer y in b...
Read more