En matematiko, grafeteorio estas la studo de grafeoj , kiuj estas matematikaj strukturoj kutimis modeligi parrilatajn rilatojn inter objektoj.
Grafeo en tiu kunteksto fariĝas supren de verdglacioj , nodoj, aŭ punktoj kiuj estas ligitaj proksime de randoj, arkoj, aŭ linioj.
Grafeo povas esti senplana, signifante ke ekzistas neniu distingo inter la du verdglacioj asociitaj kun ĉiu rando, aŭ ĝiaj randoj povas esti direktitaj de unu vertico ĝis alia;
vidu Grafeo (diskreta matematiko) por pli detalaj difinoj kaj por aliaj varioj en la specoj de grafo kiuj estas ofte pripensitaj.
Grafeoj estas unu el la ĉefaj studobjektoj en diskreta matematiko.
#000001
Rilati al la glosaro de grafeteorio por bazaj difinoj en grafeteorio.
#000002
Subgraphs, induktitaj subgrafoj, kaj neplenaĝuloj
#000003
La sekvantaroj estas kelkaj el la pli bazaj manieroj difini grafeoj kaj rilataj matematikaj strukturoj.
#000004
En la plej ordinara racio de la esprimo, [1] grafeo estas orda duopo G
V, E) konsistanta el aro V de verdglacioj aŭ nodoj aŭ punktoj kune kun aro E de randoj aŭ arkoj aŭ linioj, kiuj estas 2-elementsubaroj de V (t.e. rando estas rilata al du verdglacioj, kaj tiu unuiĝo prenas la formon de la neordigita paro konsistante el tiuj du verdglacioj).
Por eviti ambiguecon, tiu speco de grafo povas esti priskribita ĝuste kiel senplana kaj simpla.
#000005
Aliaj sencoj de grafeo devenas de malsamaj konceptoj de la randaro.
En unu pli da ĝeneraligita nocio, [2] V estas aro kune kun rilato de incidenco kiu partneroj kun ĉiu rando du verdglacioj.
En alia ĝeneraligita nocio, E estas Multaro de neordigitaj paroj de (ne nepre apartaj) verdglacioj.
Multaj verkintoj nomas tiun specon de objekto multigrafo aŭ pseŭdografo.
#000006
Ĉiuj tiuj variaĵoj kaj aliaj estas priskribitaj pli plene malsupre.
#000007
La verdglacioj apartenantaj al rando estas nomitaj la finoj aŭ finverdglacioj de la rando.
Vertico povas ekzisti en grafeo kaj ne aparteni al rando.
#000008
, grafeoteoriuloj kutime uzas la iom pli mallongan notacioksy.
#000010
Grafeoj povas esti utiligitaj por modeligi multajn specojn de rilatoj kaj procezojn en fiziko, biologia, [4] socia kaj informsistemoj.
Multaj praktikaj problemoj povas esti reprezentitaj per grafeoj.
Emfazante ilia aplikiĝo al real-mondaj sistemoj, la esprimo reto foje estas difinita por signifi grafeon en kiu atributoj (ekz. nomoj) estas rilataj al la nodoj kaj/aŭ randoj.
#000011
En komputado, grafeoj estas utiligitaj por reprezenti retojn de komunikado, datenorganizo, komputilaj aparatoj, la fluo de komputado, ktp.
Por kazo, la ligstrukturo de retejo povas esti reprezentita per direktita grafeo, en kiu la verdglacioj reprezentas retpaĝojn kaj direktitajn randojn reprezentas ligilojn de unu paĝo ĝis alia.
Simila aliro povas esti prenita al problemoj en socia amaskomunikilaro, [5] vojaĝado, biologio, integracirkvita dezajno, kaj multaj aliaj kampoj.
La evoluo de algoritmoj por pritrakti grafeojn estas tial de grava intereso en komputado.
La transformo de grafeoj ofte estas formaligita kaj reprezentita per grafeaj reverksistemoj.
Komplementaj al grafeaj transform sistemoj temigantaj regul-bazitan en-memoran manipuladon de grafeoj estas grafeodatumbazoj adaptitaj direkte al transakcio-monŝranko, persista stokado kaj pridemandado de grafe-strukturitaj datenoj.
#000012
Grafe-teoriaj metodoj, en diversaj formoj, pruvis precipe utilaj en lingvistiko, ĉar natura lingvo ofte pruntedonas sin bone al diskreta strukturo.
Tradicie, sintakso kaj kompona semantiko sekvas arb-bazitajn strukturojn, kies esprimkapablo kuŝas en la principo de kompositioneco, modeligita en hierarkia grafeo.
Pli nuntempaj aliroj kiel ekzemple ĉef-movita frazostrukturgramatiko modeligas la sintakson de natura lingvo uzado tajpis trajtostrukturojn, kiuj estas direktitaj aciklajn kurvojn.
Ene de vortfarada semantiko, aparte kiel aplikite al komputiloj, modeliganta vortsignifo estas pli facila kiam antaŭfiksita vorto estas komprenita laŭ rilataj vortoj;
semantikaj retoj estas tial gravaj en komputa lingvoscienco.
Tamen, aliaj metodoj en fonologio (ekz. optimumeca teorio, kiu utiligas kradgrafojn) kaj morfologio (ekz. finhav-ŝtata morfologio, uzi finhav-ŝtatajn transduktilojn) estas oftaj en la analizo de lingvo kiel grafeo.
Efektive, la utileco de tiu areo de matematiko al lingvistiko havas portitajn organizojn kiel ekzemple TextGraphs, same kiel diversaj "Retaj" projektoj, kiel ekzemple WordNet, VerbNet, kaj aliaj.
#000013
Grafeteorio ankaŭ estas vaste utiligita en sociologio kiel maniero, ekzemple, mezuri la prestiĝon de aktoroj aŭ por esplori onidiron disvastiĝantan, precipe helpe de sociareta analizo softvaro.
Sub la ombrelo de sociaj retoj estas multaj malsamaj specoj de grafoj.
Konateco- kaj amikecgrafoj priskribas ĉu homoj scias unu la alian.
Influografoj modeligas ĉu certaj homoj povas influi la konduton de aliaj.
Finfine, kunlaborgrafoj modeligas ĉu du homoj laboras kune laŭ speciala maniero, kiel ekzemple aktorado en filmo kune.
#000015
Same, grafeteorio estas utila en biologio kaj konservado-iniciatoj kie vertico povas reprezenti regionojn kie certaj specioj ekzistas (aŭ enloĝas) kaj la randoj reprezentas migradpadojn aŭ movadon inter la regionoj.
Tiuj informoj estas gravaj dum rigardado reproduktopadronojn aŭ spurante la disvastiĝon de malsano, parazitojn aŭ kiel ŝanĝoj al la movado povas influi aliajn speciojn.
#000016
En matematiko, grafeoj estas utilaj en geometrio kaj certaj partoj de topologio kiel ekzemple noda teorio.
Algebra grafeteorio havas proksimajn ligilojn kun teorio de grupoj.
#000017
Grafeostrukturo povas esti etendita asignante pezon al ĉiu rando de la grafeo.
Grafeoj per pezoj, aŭ pezbalancitaj grafeoj, estas utiligitaj por reprezenti strukturojn en kiuj parrilataj ligoj havas kelkajn nombrvalorojn.
Ekzemple, se grafeo reprezentas vojaron, la pezoj povus reprezenti la longon de ĉiu vojo.
Povas ekzisti pluraj pezoj asociitaj kun ĉiu rando, inkluzive de distanco (kiel en la antaŭa ekzemplo), vojaĝdaŭro, aŭ mona kosto.
Tiaj pezbalancitaj grafeoj estas ofte utiligitaj por programi tiu de GPS, kaj vojaĝad-planadajn serĉilojn kiuj komparas flugtempojn kaj kostojn.
#000018
La papero skribita fare de Leonhard Euler en la Sep pontoj en Königsberg kaj publikigita en 1736 estas rigardita kiel la unua papero en la historio de grafeteorio.
Tiu papero, same kiel tiu skribita de Vandermonde en la kavalirproblemo, daŭrigita kun la analizositus iniciatita fare de Leibniz.
Eŭlera formulo rilatigante la nombron da randoj, verdglacioj, kaj vizaĝoj de konveksa pluredro estis studitaj kaj ĝeneraligitaj fare de Cauchy [10] kaj L'Huilier, [11] kaj reprezentas la komencon de la branĉo de matematiko konata kiel topologio.
#000019
Pli ol unu jarcenton post la artikolo de Euler sur la pontoj de Königsberg kaj dum Listing lanĉis la koncepton de topologio, Cayley estis kondukita per intereso al aparte analizaj formoj ekestiĝantaj de diferenciala kalkulo por studi akuratan klason de grafeoj, la arboj .
Tiu studo havis multajn implicojn por teoria kemio.
La teknikoj li uzis plejparte konzernon la listigo de grafeoj kun specialaj trajtoj.
Listiga grafeteorio tiam ekestiĝis de la rezultoj de Cayley kaj la fundamentaj rezultoj publikigitaj fare de Pólya inter 1935 kaj 1937.
Tiuj estis ĝeneraligitaj fare de De Bruijn en 1959.
Cayley interligis siajn rezultojn sur arboj kun nuntempaj studoj de kemia kunmetaĵo.
La fuzio de ideoj de matematiko kun tiuj de kemio komenciĝis kio fariĝis parto de la norma terminologio de grafeteorio.
#000020
Aparte, la esprimo "grafeo" estis lanĉita fare de Sylvester en artikolo publikigita en 1878 en Naturo , kie li desegnas analogecon inter "kvantic-Invariantoj" kaj "ko-variaĵoj" de algebro kaj molekulajn diagramojn: [14]
#000021
Ĉiu Invarianto kaj ko-variaĵo tiel iĝas esprimeblaj de grafeo ĝuste identa kun Kekuléan diagramo aŭ kemikograf.
mi donas regulon por la geometria multipliko de grafeoj, t.e. por konstruado de grafeo al la produkto de en- aŭ ko-variaĵoj kies apartaj grafeoj ricevas.
"(kursivo kiel en la originalo).
#000022
La unua lernolibro en grafeteorio estis skribita fare de Dénes Kőnig, kaj publikigis en 1936.
Alia libro de Frank Harary, publikigita en 1969, estis "konsiderita la mondo super por esti la definitiva lernolibro pri la subjekto", [16] kaj rajtigis matematikistojn, apotekistojn, elektroinĝenierojn kaj sociaj sciencistoj paroli al unu la alian.
Harary donacis ĉiujn la tantiemo por financi la Pólyan Premion.
#000023
Unu el la plej famaj kaj stimulaj problemoj en grafeteorio estas la kvar kolorproblemo: "ĉu ĝi Estas vera tiel ajna mapo desegnita en la aviadilo povas havi sian regionkolorajn kun kvar koloroj, en tia maniero kiel ke ĉiuj du regionoj havantaj oftan limon havas malsamajn kolorojn?"
Tiu problemo unue estis prezentita fare de Francis Guthrie en 1852 kaj ĝia unua skriba rekordo estas en letero de De Morgan alparolita al Hamilton la saman jaron.
Multaj malĝustaj pruvoj estis proponitaj, inkluzive de tiuj fare de Cayley, Kempe, kaj aliaj.
La studo kaj la ĝeneraligo de tiu problemo de Tait, Heawood, Ramsey kaj Hadwiger kaŭzis la studon de la kolorecoj de la grafeoj enkonstruitaj sur surfacoj kun arbitra genro.
Tait_ estas reformulo generita nova klaso de problemoj, la faktorigadproblemoj, precipe studis de Petersen kaj Kőnig.
La verkoj de Ramsey sur kolorigoj kaj pli speciale la rezultoj akiritaj fare de Turán en 1941 estis ĉe la origino de alia branĉo de grafeteorio, ekstremal-grafeteorio .
#000024
La kvar kolorproblemo restis neklarigita por pli ol jarcento.
En 1969 Heinrich Heesch publikigis metodon por solvado de la problemo uzante komputilojn.
Komputil-helpitpruvo produktita en 1976 de Kenneth Appel kaj Wolfgang Haken faras fundamentan uzon de la nocio de "eligi" evoluigite fare de Heesch.
La pruvo implikis kontroli la trajtojn de 1,936 konfiguracioj de komputilo, kaj ne estis plene akceptita tiutempe pro sia komplekseco.
Pli simpla pruvo pripensanta nur 633 konfiguraciojn dudek jarojn poste ricevis fare de Robertson, Seymour, Sanders kaj Tomaso.
#000025
La sendependa evoluo de topologio de 1860 kaj 1930 sterkis grafeteorion reen tra la verkoj de Jordanio, Kuratowski kaj Whitney.
Alia grava faktoro de ofta evoluo de grafeteorio kaj topologio venis de la uzo de la teknikoj de moderna algebro.
La unua ekzemplo de tia uzo venas de la laboro de la fizikisto Gustav Robert Kirchhoff, kiu publikigis en 1845 la cirkvitleĝojn de sia Kirchhoff por kalkulado de la tensio kaj fluo en elektraj serilokaroj.
#000026
La enkonduko de probabilistaj metodoj en grafeteorio, precipe en la studo de Erdős kaj Rényi de la asimptota probableco de grafeokonektebleco, kaŭzis ankoraŭ alian branĉon, konatan kiel hazarda grafeteorio , kiu estis fruktodona fonto de grafe-teoriaj rezultoj.
#000027
Grafeoj estas reprezentitaj vide tirante punkton aŭ cirklon por ĉiu vertico, kaj tirante arkon inter du verdglacioj se ili estas ligitaj per rando.
Se la grafeo estas reĝisorita, la direkto estas indikita tirante sagon.
#000028
Grafeodesegnaĵo ne devus esti konfuzita kun la grafeo mem (la abstrakta, ne-vida strukturo) kia ekzistas pluraj manieroj strukturi la grafeodesegnaĵon.
Ĉiu kiu aferoj estas kiuj verdglacioj estas ligitaj al kiuj aliaj proksime de kiom multaj randoj kaj ne la preciza enpaĝigo.
En praktiko, estas ofte malfacile decidi ĉu du desegnaĵoj reprezentu la saman grafeon.
Depende de la problemdomajno kelkaj enpaĝigoj povas esti pli bone taŭgaj kaj pli facilaj por kompreni ol aliaj.
#000029
La pionira laboro de W. T. Tutte estis tre influa pri la temo de grafeodesegnaĵo.
Inter aliaj atingoj, li lanĉis la uzon de liniaj algebraj metodoj por akiri grafeodesegnaĵojn.
#000030
Grafeodesegnaĵo ankaŭ povas esti dirita ampleksi problemojn kiuj traktas la krucantan nombron kaj ĝiajn diversajn ĝeneraligojn.
La krucanta nombro da grafeo estas la mimimumnombro de intersekciĝoj inter randoj kiujn desegnaĵo de la grafeo en la aviadilo devas enhavi.
Por planar grafeo, la krucanta nombro estas nul de difino.
#000031
Ekzistas malsamaj manieroj stoki grafeojn en komputilsistemo.
La datenstrukturo uzita dependas de kaj la grafeostrukturo kaj la algoritmo uzita por manipulado de la grafeo.
Teorie oni povas distingi inter listo kaj matricstrukturoj sed en konkretaj aplikoj la plej bona strukturo ofte estas kombinaĵo de ambaŭ.
Listigu strukturojn estas ofte preferitaj por malabundaj grafeoj kiam ili havas pli malgrandajn memorpostulojn.
Matric strukturoj aliflanke disponigas pli rapidan aliron por kelkaj aplikoj sed povas konsumi enormajn kvantojn de memoro.
#000033
Listostrukturoj inkludas la incidencliston, aron de paroj de verdglacioj, kaj la apudecliston, kiu aparte listigas la najbarojn de ĉiu vertico: Tre kiel la incidenclisto, ĉiu vertico havas liston de kiu al verdglacioj ĝi estas najbaraj.
#000034
Matricstrukturoj inkludas la incidencmatricon, matricon de 0's kaj 1's kies vicoj reprezentas verdglaciojn kaj kies kolonoj reprezentas randojn, kaj la apudecomatrico, en kiuj kaj la vicoj kaj kolonoj estas indeksitaj per verdglacioj.
En ambaŭ kazoj 1 indikas du apudajn objektojn kaj 0 indikas du ne-apudajn objektojn.
La Laplaciana matrico estas modifita formo de la apudecomatrico kiu asimilas informojn pri la gradoj da la verdglacioj, kaj estas utila en kelkaj kalkuloj kiel ekzemple la teoremo de Kirchhoff sur la nombro da enhavado de arboj de grafeo.
La distancmatrico, kiel la apudecomatrico, havas kaj siajn vicojn kaj kolonojn indeksitajn de verdglacioj, sed prefere ol enhavado 0 aŭ 1 en ĉiu ĉelo ĝi enhavas la longon de plej mallonga pado inter du verdglacioj.
#000035
Ekzistas granda literaturo sur grafika listigo: la problemo de nombrado de grafeorenkontiĝo precizigis kondiĉojn.
Iuj el tiu laboro estas trovitaj en Harary kaj Palmer (1973).
#000036
Ofta problemo, nomita la subgrafa izomorfioproblemo, trovas fiksan grafeon kiel subgrafo en antaŭfiksita grafeo.
Unu kialo esti interesita pri tia demando estas tiel multaj grafeotrajtoj estas heredaj por subgrafoj, kio signifas ke grafeo havas la posedaĵon se kaj nur se ĉiuj subgrafoj havas ĝin ankaŭ.
Bedaŭrinde, trovi maksimumajn subgrafojn de certa speco ofte estas Np-kompleta problemo.
#000037
Trovado de la plej grandan kompletan subgrafon estas nomita la klikproblemo (Np-kompleta).
#000038
Simila problemo trovas induktitajn subgrafojn en antaŭfiksita grafeo.
Denove, kelkaj gravaj grafeotrajtoj estas heredaj kun respekto al induktitaj subgrafoj, kio signifas ke grafeo havas posedaĵon se kaj nur se ĉio induktite subgrafoj ankaŭ havas ĝin.
Trovi maksimumajn induktitajn subgrafojn de certa speco ankaŭ estas ofte Np-kompleta.
#000039
Trovante la plej granda edgeles induktis subgrafon aŭ sendependa aro estas nomita la sendependa arproblemo (Np-kompleta).
#000040
Daŭre alia tia problemo, la negrava retenproblemo, devas trovi fiksan grafeon kiel minora de antaŭfiksita grafeo.
A-minora aŭ subentreprenjono de grafeo estas ajna grafeo akirita prenante subgrafon kaj kuntirante kelkajn (aŭ neniujn) randojn.
Multaj grafeotrajtoj estas heredaj por neplenaĝuloj, kio signifas ke grafeo havas posedaĵon se kaj nur se ĉiuj neplenaĝuloj havas ĝin ankaŭ.
#000041
Grafeo estas planar se ĝi enhavas kiel minora nek la plenan dukoloran grafeon K 3,3 (vidu la Tridometan problemon) nek la plenan grafeon K 5.
#000042
Simila problemo, la subsekcia retenproblemo, devas trovi fiksan grafeon kiel subsekcio de antaŭfiksita grafeo.
Subsekcio aŭ homeomorfio de grafeo estas ajna grafeo akirita subdividante kelkajn (aŭ neniujn) randojn.
Subsekcioreteno estas rilata grafei trajtojn kiel ekzemple planareco.
#000043
Grafeo estas planar se ĝi enhavas kiel subsekcio nek la plenan dukoloran grafeon K 3,3 nek la plenan grafeon K 5.
#000044
Alia problemo en subsekcioreteno estas Kelmans-Seymour supozo:
#000045
Ĉiu 5-vertic-ligita grafeo kiu ne estas planar enhavas subsekcion de la 5-vertica plena grafeo K 5.
#000046
Alia klaso de problemoj devas fari kun la amplekso al kiu diversaj specioj kaj ĝeneraligoj de grafeoj estas determinitaj memstare punkt-forigitaj subgrafoj.
#000047
Multaj problemoj kaj teoremoj en grafeteorio devas fari kun diversaj manieroj de kolorigaj grafeoj.
Tipe, oni estas interesita pri kolorigado de grafeo tiel ke neniuj du apudaj verdglacioj havas la saman koloron, aŭ kun aliaj similaj restriktoj.
Oni ankaŭ povas pripensi kolorigajn randojn (eventuale tiel ke neniuj du koincidaj randoj estas la sama koloro), aŭ aliajn variojn.
Inter la famaj rezultoj kaj supozoj koncerne grafeokolorecon estas la sekvantaj:
#000048
Limaj modeligadoteorioj koncernas familiojn de direktitaj grafeoj ligitaj fare de parta ordo.
En tiuj aplikoj, grafeoj estas ordonitaj per specifeco, signifante ke pli da limigitaj grafeoj - kiuj estas pli specifaj kaj tiel enhavas pli granda informkvanto - estas inkluditaj per tiuj kiuj estas pli ĝeneralaj.
Operacioj inter grafeoj inkludas analizi la direkton de subsumption-rilato inter du grafeoj, se entuten, kaj komputikografeunuigon.
La unuigo de du argumentografoj estas difinita kiel la plej ĝenerala grafeo (aŭ la komputado de tio) kun kiu estas kongruaj (t.e. enhavas ĉion el la informoj en) la enigaĵoj, se tia grafeo ekzistas;
#000050
Por limkadroj kiuj estas strikte komponaj, grafeunuigo estas la sufiĉa satisfiabileco kaj kombinaĵfunkcio.
Bonkonataj aplikoj inkludas aŭtomatan teoremon pruvantan kaj modeligantan la pliprofundigon de lingvkonstruaĵo.
#000051
Ekzistas multaj problemoj ekestiĝantaj precipe de aplikoj kiuj povas fari kun diversaj nocioj de fluoj en retoj, ekzemple:
#000053
Kovroproblemoj en grafeoj estas specifaj kazoj de subgraph-verdiktaj problemoj, kaj ili tendencas esti proksime rilatitaj al la klikproblemo aŭ la sendependa metita problemo.
#000054
Putriĝo, difinita kiel dividado de la randaro de grafeo (kun same multaj verdglacioj kiel necesa akompanado la randoj de ĉiu parto de la sekcio), havas vastan gamon de demando.
Ofte, estas postulate malkonstrui grafeon en subgrafojn izomorfaj al fiksa grafeo;
ekzemple, malkonstruante plenan grafeon en Hamiltonian-ciklojn.
Aliaj problemoj precizigas familion de grafeoj en kiuj antaŭfiksita grafeo devus esti malkonstruita, ekzemple, familion de cikloj, aŭ malkonstruante plena grafeo K n en n − 1 precizigitajn arbojn havante, respektive, 1, 2, 3, ...
#000055
Arboricity, putriĝo en tiel malmultajn arbarojn kiel eble
Cikla duoblokovro, putriĝo en kolekton de cikloj kovrantaj ĉiun randon ekzakte dufoje
Randkoloreco, putriĝo en tiel malmultajn akordigojn kiel eble
Grafeofaktorigado, putriĝo de regula grafeo en regulajn subgrafojn de antaŭfiksitaj gradoj
#000057
Multaj problemoj implikas karakterizi la membrojn de diversaj klasoj de grafeoj.
Kelkaj ekzemploj de tiaj demandoj estas malsupre:
#000058
Listigante la membrojn de klaso
Karakterizante klason laŭ malpermesitaj substrukturoj
Konstatante rilatojn inter klasoj (ekz. oni propertyas de grafeoj implicas alian)
Trovante efikajn algoritmojn por decidi membrecon en klaso
Verdiktoreprezentantaroj por membroj de klaso
#000059
Listo de neklarigitaj problemoj en grafeteorio
#000060
Diferencialaj ekvacioj / dinamikaj sistemoj
#000065
Prezento de scio kaj rezonado
#000066
problemo de kunigado de geedzoj
#000067
Reprezentado de grafeo Glosaro de grafeteorio
#000068
Grafeteorio estas branĉo de matematiko, kiu okupiĝas pri grafeoj. La ĉefnocio de la teorio, grafeo, difineblas kiel aro de verticoj (punktoj) kaj aro de eĝoj (linieroj), kiuj ligas kelkajn parojn de verticoj. Ekzemplo de grafeo estas reto de metroo, kie la aro de la stacioj respondas al la verticoj kaj la aro de la linieroj (inter po du stacioj) al la eĝoj de grafeo.
#000069
La problemo pri la sep pontoj de Königsberg estas klasika problemo de grafeteorio; la solvo estas facila el grafoteoria vidpunkto.
#000070
Sinonimoj de grafeteorio estas grafeiko kaj teorio de grafeoj. Anstataŭ la termino "grafeo", en literaturo oni povas vidi ankaŭ la terminojn grafo kaj grafio.
#000071