[{"text_idx": "#000001", "text": "En matematiko, grafeteorio estas la studo de grafeoj , kiuj estas matematikaj strukturoj kutimis modeligi parrilatajn rilatojn inter objektoj.\nGrafeo en tiu kunteksto farig\u0302as supren de verdglacioj , nodoj, au\u0306 punktoj kiuj estas ligitaj proksime de randoj, arkoj, au\u0306 linioj.\nGrafeo povas esti senplana, signifante ke ekzistas neniu distingo inter la du verdglacioj asociitaj kun c\u0302iu rando, au\u0306 g\u0302iaj randoj povas esti direktitaj de unu vertico g\u0302is alia;\nvidu Grafeo (diskreta matematiko) por pli detalaj difinoj kaj por aliaj varioj en la specoj de grafo kiuj estas ofte pripensitaj.\nGrafeoj estas unu el la c\u0302efaj studobjektoj en diskreta matematiko."}, {"text_idx": "#000002", "text": "Rilati al la glosaro de grafeteorio por bazaj difinoj en grafeteorio."}, {"text_idx": "#000003", "text": "Subgraphs, induktitaj subgrafoj, kaj neplenag\u0302uloj"}, {"text_idx": "#000004", "text": "La sekvantaroj estas kelkaj el la pli bazaj manieroj difini grafeoj kaj rilataj matematikaj strukturoj."}, {"text_idx": "#000005", "text": "En la plej ordinara racio de la esprimo, [1] grafeo estas orda duopo G\nV, E) konsistanta el aro V de verdglacioj au\u0306 nodoj au\u0306 punktoj kune kun aro E de randoj au\u0306 arkoj au\u0306 linioj, kiuj estas 2-elementsubaroj de V (t.e. rando estas rilata al du verdglacioj, kaj tiu unuig\u0302o prenas la formon de la neordigita paro konsistante el tiuj du verdglacioj).\nPor eviti ambiguecon, tiu speco de grafo povas esti priskribita g\u0302uste kiel senplana kaj simpla."}, {"text_idx": "#000006", "text": "Aliaj sencoj de grafeo devenas de malsamaj konceptoj de la randaro.\nEn unu pli da g\u0302eneraligita nocio, [2] V estas aro kune kun rilato de incidenco kiu partneroj kun c\u0302iu rando du verdglacioj.\nEn alia g\u0302eneraligita nocio, E estas Multaro de neordigitaj paroj de (ne nepre apartaj) verdglacioj.\nMultaj verkintoj nomas tiun specon de objekto multigrafo au\u0306 pseu\u0306dografo."}, {"text_idx": "#000007", "text": "C\u0302iuj tiuj variaj\u0302oj kaj aliaj estas priskribitaj pli plene malsupre."}, {"text_idx": "#000008", "text": "La verdglacioj apartenantaj al rando estas nomitaj la finoj au\u0306 finverdglacioj de la rando.\nVertico povas ekzisti en grafeo kaj ne aparteni al rando."}, {"text_idx": "#000010", "text": ", grafeoteoriuloj kutime uzas la iom pli mallongan notacioksy."}, {"text_idx": "#000011", "text": "Grafeoj povas esti utiligitaj por modeligi multajn specojn de rilatoj kaj procezojn en fiziko, biologia, [4] socia kaj informsistemoj.\nMultaj praktikaj problemoj povas esti reprezentitaj per grafeoj.\nEmfazante ilia aplikig\u0302o 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\u0306 randoj."}, {"text_idx": "#000012", "text": "En komputado, grafeoj estas utiligitaj por reprezenti retojn de komunikado, datenorganizo, komputilaj aparatoj, la fluo de komputado, ktp.\nPor kazo, la ligstrukturo de retejo povas esti reprezentita per direktita grafeo, en kiu la verdglacioj reprezentas retpag\u0302ojn kaj direktitajn randojn reprezentas ligilojn de unu pag\u0302o g\u0302is alia.\nSimila aliro povas esti prenita al problemoj en socia amaskomunikilaro, [5] vojag\u0302ado, biologio, integracirkvita dezajno, kaj multaj aliaj kampoj.\nLa evoluo de algoritmoj por pritrakti grafeojn estas tial de grava intereso en komputado.\nLa transformo de grafeoj ofte estas formaligita kaj reprezentita per grafeaj reverksistemoj.\nKomplementaj al grafeaj transform sistemoj temigantaj regul-bazitan en-memoran manipuladon de grafeoj estas grafeodatumbazoj adaptitaj direkte al transakcio-mons\u0302ranko, persista stokado kaj pridemandado de grafe-strukturitaj datenoj."}, {"text_idx": "#000013", "text": "Grafe-teoriaj metodoj, en diversaj formoj, pruvis precipe utilaj en lingvistiko, c\u0302ar natura lingvo ofte pruntedonas sin bone al diskreta strukturo.\nTradicie, sintakso kaj kompona semantiko sekvas arb-bazitajn strukturojn, kies esprimkapablo kus\u0302as en la principo de kompositioneco, modeligita en hierarkia grafeo.\nPli nuntempaj aliroj kiel ekzemple c\u0302ef-movita frazostrukturgramatiko modeligas la sintakson de natura lingvo uzado tajpis trajtostrukturojn, kiuj estas direktitaj aciklajn kurvojn.\nEne de vortfarada semantiko, aparte kiel aplikite al komputiloj, modeliganta vortsignifo estas pli facila kiam antau\u0306fiksita vorto estas komprenita lau\u0306 rilataj vortoj;\nsemantikaj retoj estas tial gravaj en komputa lingvoscienco.\nTamen, aliaj metodoj en fonologio (ekz. optimumeca teorio, kiu utiligas kradgrafojn) kaj morfologio (ekz. finhav-s\u0302tata morfologio, uzi finhav-s\u0302tatajn transduktilojn) estas oftaj en la analizo de lingvo kiel grafeo.\nEfektive, 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."}, {"text_idx": "#000015", "text": "Grafeteorio ankau\u0306 estas vaste utiligita en sociologio kiel maniero, ekzemple, mezuri la prestig\u0302on de aktoroj au\u0306 por esplori onidiron disvastig\u0302antan, precipe helpe de sociareta analizo softvaro.\nSub la ombrelo de sociaj retoj estas multaj malsamaj specoj de grafoj.\nKonateco- kaj amikecgrafoj priskribas c\u0302u homoj scias unu la alian.\nInfluografoj modeligas c\u0302u certaj homoj povas influi la konduton de aliaj.\nFinfine, kunlaborgrafoj modeligas c\u0302u du homoj laboras kune lau\u0306 speciala maniero, kiel ekzemple aktorado en filmo kune."}, {"text_idx": "#000016", "text": "Same, grafeteorio estas utila en biologio kaj konservado-iniciatoj kie vertico povas reprezenti regionojn kie certaj specioj ekzistas (au\u0306 enlog\u0302as) kaj la randoj reprezentas migradpadojn au\u0306 movadon inter la regionoj.\nTiuj informoj estas gravaj dum rigardado reproduktopadronojn au\u0306 spurante la disvastig\u0302on de malsano, parazitojn au\u0306 kiel s\u0302ang\u0302oj al la movado povas influi aliajn speciojn."}, {"text_idx": "#000017", "text": "En matematiko, grafeoj estas utilaj en geometrio kaj certaj partoj de topologio kiel ekzemple noda teorio.\nAlgebra grafeteorio havas proksimajn ligilojn kun teorio de grupoj."}, {"text_idx": "#000018", "text": "Grafeostrukturo povas esti etendita asignante pezon al c\u0302iu rando de la grafeo.\nGrafeoj per pezoj, au\u0306 pezbalancitaj grafeoj, estas utiligitaj por reprezenti strukturojn en kiuj parrilataj ligoj havas kelkajn nombrvalorojn.\nEkzemple, se grafeo reprezentas vojaron, la pezoj povus reprezenti la longon de c\u0302iu vojo.\nPovas ekzisti pluraj pezoj asociitaj kun c\u0302iu rando, inkluzive de distanco (kiel en la antau\u0306a ekzemplo), vojag\u0302dau\u0306ro, au\u0306 mona kosto.\nTiaj pezbalancitaj grafeoj estas ofte utiligitaj por programi tiu de GPS, kaj vojag\u0302ad-planadajn serc\u0302ilojn kiuj komparas flugtempojn kaj kostojn."}, {"text_idx": "#000019", "text": "La papero skribita fare de Leonhard Euler en la Sep pontoj en Ko\u0308nigsberg kaj publikigita en 1736 estas rigardita kiel la unua papero en la historio de grafeteorio.\nTiu papero, same kiel tiu skribita de Vandermonde en la kavalirproblemo, dau\u0306rigita kun la analizositus iniciatita fare de Leibniz.\nEu\u0306lera formulo rilatigante la nombron da randoj, verdglacioj, kaj vizag\u0302oj de konveksa pluredro estis studitaj kaj g\u0302eneraligitaj fare de Cauchy [10] kaj L'Huilier, [11] kaj reprezentas la komencon de la branc\u0302o de matematiko konata kiel topologio."}, {"text_idx": "#000020", "text": "Pli ol unu jarcenton post la artikolo de Euler sur la pontoj de Ko\u0308nigsberg kaj dum Listing lanc\u0302is la koncepton de topologio, Cayley estis kondukita per intereso al aparte analizaj formoj ekestig\u0302antaj de diferenciala kalkulo por studi akuratan klason de grafeoj, la arboj .\nTiu studo havis multajn implicojn por teoria kemio.\nLa teknikoj li uzis plejparte konzernon la listigo de grafeoj kun specialaj trajtoj.\nListiga grafeteorio tiam ekestig\u0302is de la rezultoj de Cayley kaj la fundamentaj rezultoj publikigitaj fare de Po\u0301lya inter 1935 kaj 1937.\nTiuj estis g\u0302eneraligitaj fare de De Bruijn en 1959.\nCayley interligis siajn rezultojn sur arboj kun nuntempaj studoj de kemia kunmetaj\u0302o.\nLa fuzio de ideoj de matematiko kun tiuj de kemio komencig\u0302is kio farig\u0302is parto de la norma terminologio de grafeteorio."}, {"text_idx": "#000021", "text": "Aparte, la esprimo \"grafeo\" estis lanc\u0302ita fare de Sylvester en artikolo publikigita en 1878 en Naturo , kie li desegnas analogecon inter \"kvantic-Invariantoj\" kaj \"ko-variaj\u0302oj\" de algebro kaj molekulajn diagramojn: [14]"}, {"text_idx": "#000022", "text": "C\u0302iu Invarianto kaj ko-variaj\u0302o tiel ig\u0302as esprimeblaj de grafeo g\u0302uste identa kun Kekule\u0301an diagramo au\u0306 kemikograf.\nmi donas regulon por la geometria multipliko de grafeoj, t.e. por konstruado de grafeo al la produkto de en- au\u0306 ko-variaj\u0302oj kies apartaj grafeoj ricevas.\n\"(kursivo kiel en la originalo)."}, {"text_idx": "#000023", "text": "La unua lernolibro en grafeteorio estis skribita fare de De\u0301nes Ko\u030bnig, kaj publikigis en 1936.\nAlia 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\u0302enierojn kaj sociaj sciencistoj paroli al unu la alian.\nHarary donacis c\u0302iujn la tantiemo por financi la Po\u0301lyan Premion."}, {"text_idx": "#000024", "text": "Unu el la plej famaj kaj stimulaj problemoj en grafeteorio estas la kvar kolorproblemo: \"c\u0302u g\u0302i Estas vera tiel ajna mapo desegnita en la aviadilo povas havi sian regionkolorajn kun kvar koloroj, en tia maniero kiel ke c\u0302iuj du regionoj havantaj oftan limon havas malsamajn kolorojn?\"\nTiu problemo unue estis prezentita fare de Francis Guthrie en 1852 kaj g\u0302ia unua skriba rekordo estas en letero de De Morgan alparolita al Hamilton la saman jaron.\nMultaj malg\u0302ustaj pruvoj estis proponitaj, inkluzive de tiuj fare de Cayley, Kempe, kaj aliaj.\nLa studo kaj la g\u0302eneraligo de tiu problemo de Tait, Heawood, Ramsey kaj Hadwiger kau\u0306zis la studon de la kolorecoj de la grafeoj enkonstruitaj sur surfacoj kun arbitra genro.\nTait_ estas reformulo generita nova klaso de problemoj, la faktorigadproblemoj, precipe studis de Petersen kaj Ko\u030bnig.\nLa verkoj de Ramsey sur kolorigoj kaj pli speciale la rezultoj akiritaj fare de Tura\u0301n en 1941 estis c\u0302e la origino de alia branc\u0302o de grafeteorio, ekstremal-grafeteorio ."}, {"text_idx": "#000025", "text": "La kvar kolorproblemo restis neklarigita por pli ol jarcento.\nEn 1969 Heinrich Heesch publikigis metodon por solvado de la problemo uzante komputilojn.\nKomputil-helpitpruvo produktita en 1976 de Kenneth Appel kaj Wolfgang Haken faras fundamentan uzon de la nocio de \"eligi\" evoluigite fare de Heesch.\nLa pruvo implikis kontroli la trajtojn de 1,936 konfiguracioj de komputilo, kaj ne estis plene akceptita tiutempe pro sia komplekseco.\nPli simpla pruvo pripensanta nur 633 konfiguraciojn dudek jarojn poste ricevis fare de Robertson, Seymour, Sanders kaj Tomaso."}, {"text_idx": "#000026", "text": "La sendependa evoluo de topologio de 1860 kaj 1930 sterkis grafeteorion reen tra la verkoj de Jordanio, Kuratowski kaj Whitney.\nAlia grava faktoro de ofta evoluo de grafeteorio kaj topologio venis de la uzo de la teknikoj de moderna algebro.\nLa unua ekzemplo de tia uzo venas de la laboro de la fizikisto Gustav Robert Kirchhoff, kiu publikigis en 1845 la cirkvitleg\u0302ojn de sia Kirchhoff por kalkulado de la tensio kaj fluo en elektraj serilokaroj."}, {"text_idx": "#000027", "text": "La enkonduko de probabilistaj metodoj en grafeteorio, precipe en la studo de Erdo\u030bs kaj Re\u0301nyi de la asimptota probableco de grafeokonektebleco, kau\u0306zis ankorau\u0306 alian branc\u0302on, konatan kiel hazarda grafeteorio , kiu estis fruktodona fonto de grafe-teoriaj rezultoj."}, {"text_idx": "#000028", "text": "Grafeoj estas reprezentitaj vide tirante punkton au\u0306 cirklon por c\u0302iu vertico, kaj tirante arkon inter du verdglacioj se ili estas ligitaj per rando.\nSe la grafeo estas reg\u0302isorita, la direkto estas indikita tirante sagon."}, {"text_idx": "#000029", "text": "Grafeodesegnaj\u0302o ne devus esti konfuzita kun la grafeo mem (la abstrakta, ne-vida strukturo) kia ekzistas pluraj manieroj strukturi la grafeodesegnaj\u0302on.\nC\u0302iu kiu aferoj estas kiuj verdglacioj estas ligitaj al kiuj aliaj proksime de kiom multaj randoj kaj ne la preciza enpag\u0302igo.\nEn praktiko, estas ofte malfacile decidi c\u0302u du desegnaj\u0302oj reprezentu la saman grafeon.\nDepende de la problemdomajno kelkaj enpag\u0302igoj povas esti pli bone tau\u0306gaj kaj pli facilaj por kompreni ol aliaj."}, {"text_idx": "#000030", "text": "La pionira laboro de W. T. Tutte estis tre influa pri la temo de grafeodesegnaj\u0302o.\nInter aliaj atingoj, li lanc\u0302is la uzon de liniaj algebraj metodoj por akiri grafeodesegnaj\u0302ojn."}, {"text_idx": "#000031", "text": "Grafeodesegnaj\u0302o ankau\u0306 povas esti dirita ampleksi problemojn kiuj traktas la krucantan nombron kaj g\u0302iajn diversajn g\u0302eneraligojn.\nLa krucanta nombro da grafeo estas la mimimumnombro de intersekcig\u0302oj inter randoj kiujn desegnaj\u0302o de la grafeo en la aviadilo devas enhavi.\nPor planar grafeo, la krucanta nombro estas nul de difino."}, {"text_idx": "#000033", "text": "Ekzistas malsamaj manieroj stoki grafeojn en komputilsistemo.\nLa datenstrukturo uzita dependas de kaj la grafeostrukturo kaj la algoritmo uzita por manipulado de la grafeo.\nTeorie oni povas distingi inter listo kaj matricstrukturoj sed en konkretaj aplikoj la plej bona strukturo ofte estas kombinaj\u0302o de ambau\u0306.\nListigu strukturojn estas ofte preferitaj por malabundaj grafeoj kiam ili havas pli malgrandajn memorpostulojn.\nMatric strukturoj aliflanke disponigas pli rapidan aliron por kelkaj aplikoj sed povas konsumi enormajn kvantojn de memoro."}, {"text_idx": "#000034", "text": "Listostrukturoj inkludas la incidencliston, aron de paroj de verdglacioj, kaj la apudecliston, kiu aparte listigas la najbarojn de c\u0302iu vertico: Tre kiel la incidenclisto, c\u0302iu vertico havas liston de kiu al verdglacioj g\u0302i estas najbaraj."}, {"text_idx": "#000035", "text": "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.\nEn ambau\u0306 kazoj 1 indikas du apudajn objektojn kaj 0 indikas du ne-apudajn objektojn.\nLa 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.\nLa distancmatrico, kiel la apudecomatrico, havas kaj siajn vicojn kaj kolonojn indeksitajn de verdglacioj, sed prefere ol enhavado 0 au\u0306 1 en c\u0302iu c\u0302elo g\u0302i enhavas la longon de plej mallonga pado inter du verdglacioj."}, {"text_idx": "#000036", "text": "Ekzistas granda literaturo sur grafika listigo: la problemo de nombrado de grafeorenkontig\u0302o precizigis kondic\u0302ojn.\nIuj el tiu laboro estas trovitaj en Harary kaj Palmer (1973)."}, {"text_idx": "#000037", "text": "Ofta problemo, nomita la subgrafa izomorfioproblemo, trovas fiksan grafeon kiel subgrafo en antau\u0306fiksita grafeo.\nUnu kialo esti interesita pri tia demando estas tiel multaj grafeotrajtoj estas heredaj por subgrafoj, kio signifas ke grafeo havas la posedaj\u0302on se kaj nur se c\u0302iuj subgrafoj havas g\u0302in ankau\u0306.\nBedau\u0306rinde, trovi maksimumajn subgrafojn de certa speco ofte estas Np-kompleta problemo."}, {"text_idx": "#000038", "text": "Trovado de la plej grandan kompletan subgrafon estas nomita la klikproblemo (Np-kompleta)."}, {"text_idx": "#000039", "text": "Simila problemo trovas induktitajn subgrafojn en antau\u0306fiksita grafeo.\nDenove, kelkaj gravaj grafeotrajtoj estas heredaj kun respekto al induktitaj subgrafoj, kio signifas ke grafeo havas posedaj\u0302on se kaj nur se c\u0302io induktite subgrafoj ankau\u0306 havas g\u0302in.\nTrovi maksimumajn induktitajn subgrafojn de certa speco ankau\u0306 estas ofte Np-kompleta."}, {"text_idx": "#000040", "text": "Trovante la plej granda edgeles induktis subgrafon au\u0306 sendependa aro estas nomita la sendependa arproblemo (Np-kompleta)."}, {"text_idx": "#000041", "text": "Dau\u0306re alia tia problemo, la negrava retenproblemo, devas trovi fiksan grafeon kiel minora de antau\u0306fiksita grafeo.\nA-minora au\u0306 subentreprenjono de grafeo estas ajna grafeo akirita prenante subgrafon kaj kuntirante kelkajn (au\u0306 neniujn) randojn.\nMultaj grafeotrajtoj estas heredaj por neplenag\u0302uloj, kio signifas ke grafeo havas posedaj\u0302on se kaj nur se c\u0302iuj neplenag\u0302uloj havas g\u0302in ankau\u0306."}, {"text_idx": "#000042", "text": "Grafeo estas planar se g\u0302i enhavas kiel minora nek la plenan dukoloran grafeon K 3,3 (vidu la Tridometan problemon) nek la plenan grafeon K 5."}, {"text_idx": "#000043", "text": "Simila problemo, la subsekcia retenproblemo, devas trovi fiksan grafeon kiel subsekcio de antau\u0306fiksita grafeo.\nSubsekcio au\u0306 homeomorfio de grafeo estas ajna grafeo akirita subdividante kelkajn (au\u0306 neniujn) randojn.\nSubsekcioreteno estas rilata grafei trajtojn kiel ekzemple planareco."}, {"text_idx": "#000044", "text": "Grafeo estas planar se g\u0302i enhavas kiel subsekcio nek la plenan dukoloran grafeon K 3,3 nek la plenan grafeon K 5."}, {"text_idx": "#000045", "text": "Alia problemo en subsekcioreteno estas Kelmans-Seymour supozo:"}, {"text_idx": "#000046", "text": "C\u0302iu 5-vertic-ligita grafeo kiu ne estas planar enhavas subsekcion de la 5-vertica plena grafeo K 5."}, {"text_idx": "#000047", "text": "Alia klaso de problemoj devas fari kun la amplekso al kiu diversaj specioj kaj g\u0302eneraligoj de grafeoj estas determinitaj memstare punkt-forigitaj subgrafoj."}, {"text_idx": "#000048", "text": "Multaj problemoj kaj teoremoj en grafeteorio devas fari kun diversaj manieroj de kolorigaj grafeoj.\nTipe, oni estas interesita pri kolorigado de grafeo tiel ke neniuj du apudaj verdglacioj havas la saman koloron, au\u0306 kun aliaj similaj restriktoj.\nOni ankau\u0306 povas pripensi kolorigajn randojn (eventuale tiel ke neniuj du koincidaj randoj estas la sama koloro), au\u0306 aliajn variojn.\nInter la famaj rezultoj kaj supozoj koncerne grafeokolorecon estas la sekvantaj:"}, {"text_idx": "#000050", "text": "Limaj modeligadoteorioj koncernas familiojn de direktitaj grafeoj ligitaj fare de parta ordo.\nEn 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\u0302eneralaj.\nOperacioj inter grafeoj inkludas analizi la direkton de subsumption-rilato inter du grafeoj, se entuten, kaj komputikografeunuigon.\nLa unuigo de du argumentografoj estas difinita kiel la plej g\u0302enerala grafeo (au\u0306 la komputado de tio) kun kiu estas kongruaj (t.e. enhavas c\u0302ion el la informoj en) la enigaj\u0302oj, se tia grafeo ekzistas;"}, {"text_idx": "#000051", "text": "Por limkadroj kiuj estas strikte komponaj, grafeunuigo estas la sufic\u0302a satisfiabileco kaj kombinaj\u0302funkcio.\nBonkonataj aplikoj inkludas au\u0306tomatan teoremon pruvantan kaj modeligantan la pliprofundigon de lingvkonstruaj\u0302o."}, {"text_idx": "#000053", "text": "Ekzistas multaj problemoj ekestig\u0302antaj precipe de aplikoj kiuj povas fari kun diversaj nocioj de fluoj en retoj, ekzemple:"}, {"text_idx": "#000054", "text": "Kovroproblemoj en grafeoj estas specifaj kazoj de subgraph-verdiktaj problemoj, kaj ili tendencas esti proksime rilatitaj al la klikproblemo au\u0306 la sendependa metita problemo."}, {"text_idx": "#000055", "text": "Putrig\u0302o, difinita kiel dividado de la randaro de grafeo (kun same multaj verdglacioj kiel necesa akompanado la randoj de c\u0302iu parto de la sekcio), havas vastan gamon de demando.\nOfte, estas postulate malkonstrui grafeon en subgrafojn izomorfaj al fiksa grafeo;\nekzemple, malkonstruante plenan grafeon en Hamiltonian-ciklojn.\nAliaj problemoj precizigas familion de grafeoj en kiuj antau\u0306fiksita grafeo devus esti malkonstruita, ekzemple, familion de cikloj, au\u0306 malkonstruante plena grafeo K n en n \u2212 1 precizigitajn arbojn havante, respektive, 1, 2, 3, ..."}, {"text_idx": "#000057", "text": "Arboricity, putrig\u0302o en tiel malmultajn arbarojn kiel eble\nCikla duoblokovro, putrig\u0302o en kolekton de cikloj kovrantaj c\u0302iun randon ekzakte dufoje\nRandkoloreco, putrig\u0302o en tiel malmultajn akordigojn kiel eble\nGrafeofaktorigado, putrig\u0302o de regula grafeo en regulajn subgrafojn de antau\u0306fiksitaj gradoj"}, {"text_idx": "#000058", "text": "Multaj problemoj implikas karakterizi la membrojn de diversaj klasoj de grafeoj.\nKelkaj ekzemploj de tiaj demandoj estas malsupre:"}, {"text_idx": "#000059", "text": "Listigante la membrojn de klaso\nKarakterizante klason lau\u0306 malpermesitaj substrukturoj\nKonstatante rilatojn inter klasoj (ekz. oni propertyas de grafeoj implicas alian)\nTrovante efikajn algoritmojn por decidi membrecon en klaso\nVerdiktoreprezentantaroj por membroj de klaso"}, {"text_idx": "#000060", "text": "Listo de neklarigitaj problemoj en grafeteorio"}, {"text_idx": "#000065", "text": "Diferencialaj ekvacioj / dinamikaj sistemoj"}, {"text_idx": "#000066", "text": "Prezento de scio kaj rezonado"}, {"text_idx": "#000067", "text": "problemo de kunigado de geedzoj"}, {"text_idx": "#000068", "text": "Reprezentado de grafeo Glosaro de grafeteorio"}, {"text_idx": "#000069", "text": "Grafeteorio estas branc\u0302o de matematiko, kiu okupig\u0302as pri grafeoj. La c\u0302efnocio de la teorio, grafeo, difineblas kiel aro de verticoj (punktoj) kaj aro de eg\u0302oj (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\u0302oj de grafeo."}, {"text_idx": "#000070", "text": "La problemo pri la sep pontoj de Ko\u0308nigsberg estas klasika problemo de grafeteorio; la solvo estas facila el grafoteoria vidpunkto."}, {"text_idx": "#000071", "text": "Sinonimoj de grafeteorio estas grafeiko kaj teorio de grafeoj. Anstatau\u0306 la termino \"grafeo\", en literaturo oni povas vidi ankau\u0306 la terminojn grafo kaj grafio."}]