agra graph

graph siddhaantamlo, ganita shaastram yokka oka saakha, oka sikharam graph anedi oke sheershaanni tolaginchadam dwara samathattamgaa cheyagala graph. tolaginchina sheershaanni graph yokka sikharam antaaru. idhi "sikharam", sikharam kaadu, endukante sikharam graph okati kante ekkuva sikharaalanu kaligi undavacchu; udaaharanaku, kaneesa naan planner graphlalo ledhaa, prati sheersham oka sikharam. sikharaala graphlalo samatalamgaa unde graphlu untaayi, eee sandarbhamlo mallii prati sheersham oka sikharam. tolaginchadaaniki sheersham laenappatikee shoonya graphnu sikhara graphga kooda lekkistaaru.
agra graphlu mainarlanu teesukune operationlo muusivaeyabadataayi mariyu graph mainer siddhaantam yokka aneka itara amsaalalo paatra poeshistaayih link laeni embedding, hodwiger yokka ooha, yδy-tagginchagala graphlu mariyu trevidth mariyu graph vyaasam madhya sambandhaalu.
lakshanaala gurtimpu mariyu gurtimpu.
agra graphlu mainarlanu teesukune operationlo moosiveyabadataayih edainaa anchu kudinchadam ledhaa edainaa anchu ledhaa sheershaanni tolaginchadam, maroka sikhara graphku daariteestundi. endukante, agrabhagamtho unna sikhara graph ayithe, appudu yea sankocham ledhaa tolagimpu migilina graph yokka samathoulyaanni samrakshistundi, alaage anchu sanghatana yokka edainaa anchu tolagimpu kooda. oka anchu sanghatana kudinchabadinatlayithe, migilina graphpy prabhavam anchu yokka itara mugimpu binduvunu tolaginchadaaniki samanam. mariyu daanini tolaginchinatlayithe, edainaa itara sheershaanni sikharamgaa enchukovachhu.
robertson-seamer siddhaantam prakaram, avi chinna-moosivesina graphla kutumbaanni yerparustaayi kabatti, agra graphlu nishiddha graph lakshanaalanu kaligi untaayi.
epex graphlu kaani ledhaa mainarga maroka naan-apex graph laeni parimitamaina aneka graphlu matrame unnaayi.
eee graphlu atyunnata graph anae lakshanaaniki "nishiddha mainarlu".
nishedhinchabadina mainarlu evaruu mainer kakapothe matrame edainaa itara graph anedi epex graph avutundi.
eee nishedhinchabadina mainarlalo peterson kutumbaaniki chendina edu graphlu, rendu mariyu yokka vidadeeyabadina unionla nundi erpadina moodu disconnect cheyabadina graphlu mariyu aneka itara graphlu unnaayi. ayithe, vaati gurinchi puurti vivarana teliyadu.
nishedhita mainarla puurti samiti teliyakapoyinappatiki, icchina graph oka epex graph kaadaa anie pareekshinchadam saadhyamavutundi, mariyu alaa ayithe, graph kosam oka epexnu leanier timelo kanugonadam saadhyamavutundi. marinta saadhaaranamgaa, edainaa sthira sthiraamkam kosam, sarala samayamlo-apex graphlanu gurtinchadam saadhyamavutundi, chaalaa sheershaala vadda jagrattagaa enchukunna konni samitini tolaginchadam oka samatala graphku daariteestundi. ayithe, idhi variable ayithe, samasya enpe-complete avutundi.
chromatic sankhya.
prati sikharam graphlo garishtamgaa aidu chromatic sankhyalu untayih antarleena samatala graphku naalugu rangu siddhaantam prakaram garishtamgaa naalugu rangulu avasaram, migilina sheershaaniki garishtamgaa oka adanapu rangu avasaram. prati 6-varna graph chinnadigaa puurti graphnu kaligi undani, prati 6-varna graph vishayamlo vaari rujuvulo eee vaastavaanni upayoginchaaruh vaaru oohaku edainaa kaneesa prati udaaharana apex graph ayi undaalani chuupimchaaru, conny 6-varna sikhara graphlu lenanduna atuvanti prati udaaharana undakudadu.
 chinnadigaa laeni prati 6-vertex-anusandhaanita graph tappanisarigaa epex graph ayi undaalani oohinchaaru. idhi niroopinchabadithe, robertson-seamer-thamus yokka hadwigger oohapai phalitam takshana parinaamam avutundi. georgensen yokka ooha niroopinchabadaledu. ayithe, idhi tappu ayithe, dheeniki parimitamaina aneka vyatiraeka udaaharanalu matrame unnaayi.
sthaanika vruksha vedalpu.
graph kutumbamlo graph vyasamu mariyu vruksha vedalpu madhya kriyaatmaka sambandhaanni paatisthe "parimita sthaanika vruksha vedalpu" untundih oka vyasamu-graph yokka vruksha vedalpu garishtamgaa unde vidhamaina function undhi. sikhara graphlaku parimitamaina sthaanika trevidth leduh grid graph yokka prati sheershaaniki sikhara sheershaanni anusandhaaninchadam dwara erpadina sikhara graphlu vruksha vedalpu mariyu vyaasam 2 kaligi untaayi, kabatti eee graphlaku vruksha vedalpu vyaasam yokka function dwara parimitam kaadu. ayithe, agra graphlu parimita sthaanika vruksha vedalputho sannihitamgaa anusandhaaninchabadi unnaih sthaanika vruksha vedalpunu parimitam chesina chinna-moosivesina graph kutumbaalu khachitamgaa vaari nishedhinchabadina mainarlalo okarigaa agra graphnu kaligi unna kutumbaalu. nishedhinchabadina mainarlalo okarigaa epex graphnu kaligi unna chinna-moosivesina graphla kutumbaanni "epex-mainer-free" anie pilustaaru. eee paribhaashato, agrashreni graphlu mariyu sthaanika vrukshasampada madhya sambandhaanni, agrashreni-mainer-free graph kutumbaalu parimita sthaanika vrukshasampadato chinna-moosivesina graph kutumbaalato samanamga untaayi anae vaastavamgaa punarudghaatinchavachchu.
parimita sthaanika trividanam anae bhavana dvimaana siddhaantaaniki aadharam, mariyu apex-mainer-free graphlapy aneka algorithmic samasyalanu khachitamgaa bahupadi-samaya algorithm ledhaa sthira-paramiti margadarshi algorithm dwara parishkarinchadaaniki anumatistundi, ledhaa bahupadi-samaya ujjaayimpu pathakaanni upayoginchi sumaruga anchanaa veyabadutundi. apex-mainer-free graph kutumbaalu graph structure siddhaantam yokka balopetam chesina samskarananu paatistaayi, idhi graph colouring mariyu travelling sales maan samasya kosam adanapu ujjaayimpu algorithamlaku daariteestundi. ayithe, eee phalitaallo konnintini apex-mainer-free graphlaku sambandhinchina nirmaana siddhaantaala dwara ekapaksha chinna-closed graph kutumbaalaku kooda vistarinchavacchu.
embededlu.
okavela sikharamtho kuudina sikharam graph ayithe, mariyu oka samatala embeddinglo anni poruguvaarini cover cheyadaaniki avasaramaina kaneesa mukhaala sankhya ayithe, appudu jaathi yokka dvi-miteeya uparitalampai ponduparachavacchuh kevalam samatala embeddingku vantenala sankhyanu jodinchandi, anni mukhalanu kaluputuu, anusandhaaninchavalasi untundi. udaaharanaku, oka bahya samatala rekhaachitraaniki (oka rekhaachitramtho) oke sheershaanni jodinchadam oka samatala rekhaachitraanni utpatti chestundi. 3-anusandhaaninchabadinappudu, athani bandham saraina sthiramaina kaarakamlo untundih prati uparitala ponduparachadaaniki kaneesam jaathi avasaram. ayithe, oka uparitala graph yokka ponduparachadam yokka saraina jaatini nirnayinchadam np-kashtam.
epex graph yokka planar bhaagam yokka saadhyamaina embeddinglanu encode cheyadaaniki spqr treelanu upayoginchadam dwara, samatalamloni graph yokka draayingnu lekkinchadam saadhyamavutundi, dheenilo oke crossinglu epex vertexnu kaligi untaayi, idhi mottam crossingla sankhyanu, bahupadi samayamlo taggistundi. ayithe, ekapaksha crossinglanu anumatinchinatlayithe, crossingla sankhyanu tagginchadam chaalaa kashtam avutundi, pratyeka sandarbhamlo kooda samatala graphku oke anchunu jodinchadam dwara erpadina sikharaala graphlu.
sikhara graphlu trimiteeya pradaesamloe anusandhaaninchaleni vidhamgaa ponduparachadaginavih graphloni prati chakram graph yokka itara lakshanaala dwara daatabadani disk yokka sarihaddugaa unde vidhamgaa vaatini ponduparachavacchu. graph yokka samatala bhaganni oka samatalamlo geeyadam dwara, sikharaanni samatalaaniki paina unchadam dwara mariyu sikharaanni daani prati poruguvaariki sarala-rekha anchulatho anusandhaaninchadam dwara eee rakamaina rekhaachitraanni pondavacchu. anusandhanam lekunda ponduparachadagina graphlu peterson kutumbamloni edu graphlanu vaari kaneesa nishedhinchabadina mainarluga kaligi unna chinna-moosivesina kutumbaanni yerparustaayi; anduvalla, eee graphlu agra graphlaku mainarluga kooda nishedhinchabaddaayi. ayithe, apex graphlu kaani anusandhanam laeni embedable graphlu unnaayi.
yδy-taggimpu.
anusandhaaninchabadina graphnu dasala kramam dwara oke sheershaaniki tagginchagaligite, prati okkati δ-y ledhaa y-δ parivartana, sweeya-loop ledhaa bahula prakkane unna tolagimpu, oka pakkapakkane unna sheershaanni tolaginchadam mariyu degree rendu yokka sheershaanni mariyu daani rendu porugu anchulanu oke anchutho bharti cheyadam dwara yδy-tagginchabadutundi.
agra graphlu mariyu anusandhanam laeni ponduparachadagina graphla maadirigaane, yδy-tagginchadagina graphlu graph mainarla krinda muusivaeyabadataayi. mariyu, anusandhanam laeni ponduparachadagina graphla maadirigaane, yδy-tagginchadagina graphlu peterson kutumbamlo edu graphlanu nishedhinchabadina mainarluga kaligi untaayi, ivi matrame nishedhinchabadina mainarlu kaadaa mariyu yδy-tagginchadagina graphlu anusandhanam laeni ponduparachadagina graphla maadirigaane unnaya anae prasnanu prerepistaayi. ayithe, neel robertson yδy-tagginchaleni sikharagra rekhaachitraaniki oka udaaharananu andinchaaru. prati epex graph anusandhanam laeni ponduparachadaginadi kabatti, idhi anusandhanam laeni ponduparachadagina conny yδy-tagginchadaginavi kaani graphlu unnayani mariyu anduvalla yδy-tagginchadagina graphlaku adanapu nishedhinchabadina mainarlu unnayani choopistundi.
robertson yokka sikharam graph chitramlo choopabadindi. rambic dodecahedron yokka degree-moodu sheershaalalo pratidaaniki oka sikhara sheershaanni anusandhaaninchadam dwara ledhaa naalugu dimensional hypercube graph yokka rendu vyaasa viruddha sheershaalanu vileenam cheyadam dwara dheenini pondavacchu. rambic dodecahedron yokka graph samathattamgaa unnanduna, robertson yokka graph oka sikharam graph. idhi kaneesa degree naalugu thoo tribhujam laeni graph, kabatti dheenini yea yδy-taggimpu dwara marchalemu.
daadaapu samatala rekhaachitraalu.
oka graph oka epex graph ayithe, daaniki oka pratyaekamaina epex undaalsina avasaram ledhu. udaaharanaku, chinna-kaneesa nonplanner graphlu "k" 5 mariyu "k" 3,3 loe, edainaa sheershaalanu sikharamgaa enchukovachhu. daadaapu samathattamaina graphnu anni sheershaalu graph yokka sikharamgaa undagala lakshanamtho samathattarahita sikharam graphga nirvachinchaaru; anduvalla, "k" 5 mariyu "k" 3,3 daadaapu samathattamgaa untaayi. athanu eee graphlanu naalugu upasamitulugaa vargeekarinchaadu, veetilo okati graphlanu kaligi untundi, (mobius nicchenalu vantivi) mobius striplo ponduparachavacchu, tadwara strip yokka oke anchu graph yokka hamiltonian chakramtho samanamga untundi. naalugu rangula siddhaantam yokka rujuvuku mundu, athanu daadaapu prati samatala rekhaachitraanni garishtamgaa naalugu rangulatho rangu veyavachani niroopinchaadu, oka chakra rekhaachitram nundi erpadina rekhaachitraalu minaha, besi bayati chakramtho, hub sheershaanni rendu prakkane unna sheershaalato bharti cheyadam dwara, dheeniki aidu rangulu avasaram. adanamgaa, oke minahaayimputo (cube yokka enimidi-vertex compliment graph) prati daadaapu planar graph projective plainpy ponduparachabadindani ayana niroopinchaaru.
edemaina, "daadaapu samatala rekhaachitram" anae padabandham chaalaa aspashtamgaa undih idhi sikharaala rekhaachitraalu, samatatta rekhaachitraaniki oka anchunu jodinchadam dwara erpadina rekhaachitraalu mariyu parimita sankhyalo mukhalanu parimita maarga vedalpu yokka "sudigaali" thoo bharti cheyadam dwara samathattamlo ponduparachabadina rekhaachitram nundi erpadina graphlanu, alaage itara takkuva khachitamaina nirvachinchina graphla samitulanu suuchimchadaaniki kooda upayoginchabadindi.
sambandhita graph taragatulu.
n" ledhaa anthakante takkuva sheershaalanu tolaginchadam dwara samathattamgaa cheyagaligithe nairoopya graphnu "n"-apex anie antaaru. 1-opex graph kooda agrasthaanamlo untundani chebutaaru.
daani prakaram, graph planner cheyadaaniki graph loe kontha anchu unte daanini tolaginchavacchu. graphnu samathookam cheyadaaniki graphlo kontha anchu unte graph anedi sankocham-opex.
saadhaaranamgaa, x anedi graphla taragati ayithe, "apex-x" graph anedi oka sheershaanni tolaginchadam dwara x taragatiki teesukuraavacchu. udaaharanaku, oka agra-rekhaachitram anedi "g" anae graph, idhi "v" anae sheershaanni kaligi untundi, antey "g-v" anedi oka rekhaachitram.

