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"););5DBl1ePuGG
-
uJkfcT7KRS5fBlhQqv,dmCSV 2rtbWqvETKjnc l3tuIPc8Kg

Popular posts from this blog

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

What is the result of assigning to std::vector::begin()? The Next CEO of Stack OverflowWhat are the differences between a pointer variable and a reference variable in C++?What does the explicit keyword mean?Concatenating two std::vectorsHow to find out if an item is present in a std::vector?Why is “using namespace std” considered bad practice?What is the “-->” operator in C++?What is the easiest way to initialize a std::vector with hardcoded elements?What is The Rule of Three?What are the basic rules and idioms for operator overloading?Why are std::begin and std::end “not memory safe”?

Image
Is there a way to save my career from absolute disaster? Why didn't Khan get resurrected in the Genesis Explosion? How to make a variable always equal to the result of some calculations? What can we do to stop prior company from asking us questions? How do we know the LHC results are robust? How does the mv command work with external drives? What is ( CFMCC ) on ILS approach chart? Between two walls Should I tutor a student who I know has cheated on their homework? How do scammers retract money, while you can’t? What happens if you roll doubles 3 times then land on "Go to jail?" What is the result of assigning to std::vector<T>::begin()? How to count occurrences of text in a file? What was the first Unix version to run on a microcomputer? Return the Closest Prime Number How did people program for Consoles with multiple CPUs? What does convergence in distribution "in the Gromov–Hausdorff" sense mean? How should I support th...
Read more

SQL Server 2016 - excessive memory grant warning on poor performing query The Next CEO of Stack OverflowFix for slow SQL_INLINE_TABLE_VALUED_FUNCTIONLarge memory grant requestsPoor performing Query -Tsql execution plan - estimated number of rows =1 Paste the PlanMSSQL - Query had to wait for memory grantRow estimates always too lowBad performance using “NOT IN”Warning about memory “Excessive Grant” in the query plan - how to find out what is causing it?Optimizing table valued function SQL ServerWhen does SQL Server warn about an Excessive Memory Grant?Warning in Execution Plan

Image
What do "high sea" and "carry" mean in this sentence? Are there any limitations on attacking while grappling? Between two walls Why do remote companies require working in the US? WOW air has ceased operation, can I get my tickets refunded? What connection does MS Office have to Netscape Navigator? What can we do to stop prior company from asking us questions? Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis How did the Bene Gesserit know how to make a Kwisatz Haderach? How does the mv command work with external drives? Rotate a column How to Reset Passwords on Multiple Websites Easily? MessageLevel in QGIS3 How did people program for Consoles with multiple CPUs? What is the result of assigning to std::vector<T>::begin()? Novel about a guy who is possessed by the divine essence and the world ends? Can we say or write : "No, it'sn't"? How to count occurren...
Read more