
nirdeshit graph

ganit mein, aur vishesh roop seey graph siddhant mein, ack nirdeshit graph (yaa degraph) ack graph haye joe nirdeshit kinaaron seey judey sheershon key ack samooh seey banaa hotaa haye, jise aksar chaap kahaa jaataa haye.
paribhasha.
aupchaarik roop seey, ack nirdeshit graph ack krambaddh jodee haye jahan
yeh ack sadharan yaa anirdisht graph seey alag haye, jisamen baad vaale koo sheershon key aniyamit jode key sandarbh mein paribhaashit kiya gayaa haye, jinhen aamtaur parr "kinare", "link" yaa "rekhaaen" kahaa jaataa haye.
uparokt paribhasha ack nirdeshit graph koo ack hii srot aur lakshya nodes key saath kaee teeron kii anumati naheen detee haye, lekin kuchh lekhak ack vyaapak paribhasha parr vichaar karate hain joe nirdeshit graph koo aise kaee chapon (arthaat, way chaap koo ack bahu-samooh honey kii anumati dete hain) kii anumati detaa haye. kabhi-kabhi inn sansthaon koo nirdeshit bahu-shilalekh (yaa bahu-shilalekh) kahaa jaataa haye.
doosari or, uparokt paribhasha ack nirdeshit graph koo loop (yaani, chaap joe seedhe nodes koo apane saath jodate hain) rakhane kii anumati detee haye, lekin kuchh lekhak ack sankeern paribhasha parr vichaar karate hain joe nirdeshit graph koo loop kii anumati naheen detee haye.
loop key binaa nirdeshit graph koo saral nirdeshit graph kahaa jaa sakata haye, jabaki loop key saath nirdeshit graph koo "loop-degraph" kahaa jaa sakata haye (nirdeshit graph key khand prakaar dekhein).
buniyaadi shabdawali.
ack chaap koo "x" seey "y" taka nirdeshit maanaa jaataa haye; "y" koo "haid" kahaa jaataa haye aur "x" koo chaap kaa "tail" kahaa jaataa haye; "y" koo "x" kaa "direct successor" kahaa jaataa haye aur "x" koo "y" kaa "direct processor" kahaa jaataa haye. yadi koee maarg "x" seey "y" kii or jaataa haye, tou "y" koo "x" kaa "uttaradhikari" aur "x" seey "pahunchane yogya" kahaa jaataa haye, aur "x" koo "y" kaa "poorvavarti" kahaa jaataa haye. chaap koo "riverse aark" kahaa jaataa haye.
loop key saath ack bahu-lipi kaa nikatata matricks purnank-moolya vaalaa matricks haye jisamen panktiyaan aur stambh sheershon key anuroop hotey hain, jahaan ack gair-vikarn pravishti "a" ij "sheersh" i "seey sheersh" j "taka chapon kii sankhya haye, aur vikarn pravishti" a "" ii "sheersh" i "parr loopon kii sankhya haye. ack nirdeshit graph kaa nikatata matricks ack taarkik matricks haye, aur haye
panktiyon aur stambhon key kramparivartan taka advitiya.
ack nirdeshit graph key liye ack anya matricks pratinidhitva isaki aapatan matricks haye.
adhik paribhashaon key liye disha dekhein.
avagunit aur bahirmukhi.
ack sheersh key liye, ack sheersh key buggle mein sir key sir kii sankhya koo sheersh kii "indegri" kahaa jaataa haye aur ack sheersh key buggle mein poonchh key sir kii sankhya koo isaki "out degree" (pedon mein "shakha kaarak" kahaa jaataa haye) kahaa jaataa haye.
aur dein. v" kii indigri koo deeg-("v") aur isaki out degree koo deeg + ("v") kahaa jaataa haye.
ack sheersh koo "srot" kahaa jaataa haye, kyonki yeh isake pratyek baahari chaap kaa mool haye. isi tarah, ack sheersh koo "sink" kahaa jaataa haye, kyonki yeh isake aaney vaale pratyek chaap kaa anta hotaa haye.
degree yog sootra" mein kahaa gayaa haye kii, ack nirdeshit graph key liye,
yadi pratyek sheersh key liye, tou graph koo "santulit nirdeshit graph" kahaa jaataa haye.
degree anukram.
ack nirdeshit graph kaa degree anukram isaki avgun aur bahirmiti jodon kii soochi haye; uparokt udaaharan key liye hamaare paas degree anukram ((2,0), (2,2), (0,2), (1,1)) haye. degree anukram ack nirdeshit graph aparivartaniya haye isaliye samroop nirdeshit graph mein samaan degree anukram hotaa haye. haalaanki, degree anukram, samanya roop seey, ack nirdeshit graph kii vishisht roop seey pehchaan naheen kartaa haye; kuchh mamalon mein, gair-samroop degraph mein samaan degree anukram hotaa haye.
nirdeshit graph praapti samasya sakaratmak purnank jode key diye gaye anukram key saath ack nirdeshit graph khojane kii samasya haye. (shoonya key peechhe key jode koo nazarandaj kiya jaa sakata haye kyonki unhein nirdeshit graph mein alag-alag sheershon kii ack upayukt sankhya jodkar tuchchh roop seey mahsoos kiya jaataa haye.) ack anukram joe kuchh nirdeshit graph kaa degree anukram haye, i.ee. jisake liye nirdeshit graph praapti samasya kaa ack samadhan haye, ise nirdeshit graphic yaa nirdeshit graphical anukram kahaa jaataa haye. iss samasya koo yaa tou cleatman-wang algorithm yaa fulkerson-chain-ensty pramey dwara hull kiya jaa sakata haye.
nirdeshit graph sampark.
ack nirdeshit graph "kamjor roop seey judaa huaa" (yaa sirf "judaa huaa") haye yadi graph key sabhi nirdeshit kinaaron koo anirdisht kinaaron key saath badalkar praapt anirdisht "antarnihit graph" ack judaa huaa graph haye.
ack nirdeshit graph "dridhata seey judaa huaa" yaa "majboot" haye yadi isamen sheershon kii pratyek jodee key liye "x" seey "y" (aur "y" seey "x") taka kaa nirdeshit maarg haye. majboot ghatak" adhikatam dridhata seey judey upgraph hain.
ack judaa huaa mool graph (yaa "pravaah graph") vaha haye jahan ack vishisht "mool sheersh" seey pratyek sheersh taka ack nirdeshit maarg maujood haye.

