Colin de Verdière graph invariant
કોલિન ડી વર્ડીયરનું અપરિવર્તન એ કોઈપણ ગ્રાફ જી માટે ગ્રાફ પરિમાણ છે, જે 1990 માં યવેસ કોલિન ડી વર્ડીયર દ્વારા રજૂ કરવામાં આવ્યું હતું. તે ચોક્કસ શ્રોડિંગર ઓપરેટરોના બીજા આઈગન વેલ્યુની મહત્તમ ગુણાકારના અભ્યાસ દ્વારા પ્રેરિત હતું. વ્યાખ્યા ચાલો શિરોબિંદુ સમૂહ સાથે લૂપલેસ સરળ આલેખ હોઈએ. પછી કોઈપણ સપ્રમાણ મેટ્રિક્સનો સૌથી મોટો કોરાંક છે જેમ કેઃ (M1) બધા માટેઃ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = જાણીતા આલેખ પરિવારોની લાક્ષણિકતા આલેખના કેટલાક જાણીતા પરિવારોને તેમના કોલિન ડી વર્ડીયર અપરિવર્તનના સંદર્ભમાં વર્ગીકૃત કરી શકાય છેઃ જો અને માત્ર ત્યારે જ જો G પાસે કોઈ ધાર ન હોય; જો અને માત્ર ત્યારે જ જો G એક રેખીય જંગલ હોય (માર્ગોનું અસંબદ્ધ જોડાણ); જો અને માત્ર ત્યારે જ જો G બાહ્ય સમતલ હોય; જો અને માત્ર ત્યારે જ જો G સમતલ હોય; જો અને માત્ર ત્યારે જ જો G R3 માં જોડાણ વિના એમ્બેડ કરી શકાય. આલેખના આ જ પરિવારો ગ્રાફના કોલિન ડી વર્ડીયર અપરિવર્તન અને તેના પૂરકની રચના વચ્ચેના જોડાણોમાં પણ દેખાય છેઃ જો એન-વર્ટેક્સ ગ્રાફનું પૂરક રેખીય જંગલ હોય, તો; જો એન-વર્ટેક્સ ગ્રાફનું પૂરક બાહ્ય સમતલ હોય, તો; જો એન-વર્ટેક્સ ગ્રાફનું પૂરક સમતલીય હોય, તો. ગ્રાફ માઇનર્સ ગ્રાફનો માઇનોર એ બીજો ગ્રાફ છે જે તેની કિનારીઓને સંકોચાઈને અને કિનારીઓ અને શિરોબિંદુઓને કાઢીને રચાય છે. કોલિન ડી વર્ડીયર અપરિવર્તનશીલ ગૌણ-એકવિધ છે, જેનો અર્થ છે કે લઘુ આલેખ લેવાથી માત્ર તેના અપરિવર્તનશીલમાં ઘટાડો થઈ શકે છે અથવા તેમાં કોઈ ફેરફાર થતો નથીઃ જો H એ G નો ગૌણ છે તો. રોબર્ટસન-સીમોર પ્રમેય મુજબ, દરેક k માટે આલેખનો એક મર્યાદિત સમૂહ H અસ્તિત્વમાં છે, જેમ કે મહત્તમ k પર અપરિવર્તનશીલ આલેખ એવા આલેખ જેવા જ હોય છે જેમાં H નો કોઈ સભ્ય ગૌણ તરીકે ન હોય. પ્રતિબંધિત સગીરના આ સમૂહને k ≤ 3 માટે સૂચિબદ્ધ કરે છે; k = 4 માટે પ્રતિબંધિત સગીરના સમૂહમાં પીટરસન પરિવારના સાત આલેખનો સમાવેશ થાય છે, કારણ કે લિંકલેસ એમ્બેડ કરી શકાય તેવા આલેખના બે લાક્ષણિકતાઓને કારણે, જેમ કે μ ≤ 4 સાથેના આલેખ અને પીટરસન પરિવારના નાના ન હોય તેવા આલેખ તરીકે. કે = 5 માટે પ્રતિબંધિત સગીરના સમૂહમાં હેવુડ પરિવારના 78 આલેખનો સમાવેશ થાય છે, અને એવું અનુમાન કરવામાં આવે છે કે ત્યાં વધુ નથી. રંગીન સંખ્યાએ અનુમાન લગાવ્યું હતું કે કોલિન ડી વર્ડીયર અપરિવર્તનશીલ એમયુ સાથેનો કોઈપણ આલેખ મહત્તમ એમયુ + 1 રંગોથી રંગીન હોઈ શકે છે. દાખલા તરીકે, રેખીય જંગલોમાં અપરિવર્તનશીલ 1 હોય છે, અને તે 2-રંગીન હોઈ શકે છે; બાહ્ય સમતલ આલેખમાં અપરિવર્તનશીલ બે હોય છે, અને તે 3-રંગીન હોઈ શકે છે; સમતલ આલેખમાં અપરિવર્તનશીલ 3 હોય છે, અને (ચાર રંગ પ્રમેય દ્વારા) તે 4-રંગીન હોઈ શકે છે. કોલિન ડી વર્ડીયર સાથે મહત્તમ ચાર અપરિવર્તનશીલ આલેખ માટે, અનુમાન સાચું રહે છે; આ લિંકલેસ એમ્બેડ કરી શકાય તેવા આલેખ છે, અને હકીકત એ છે કે તેમની પાસે મહત્તમ પાંચ રંગીન સંખ્યા છે, જે કે6-નાના-મુક્ત આલેખ માટે હેડવિગર અનુમાન દ્વારા પુરાવાઓનું પરિણામ છે. અન્ય ગુણધર્મો જો આલેખમાં ક્રાસિંગ નંબર હોય, તો તેમાં કોલિન ડી વર્ડીયર અપરિવર્તનશીલ હોય છે. દાખલા તરીકે, બે કુરાટોવ્સ્કી આલેખ અને બંનેને એક જ ક્રોસિંગ સાથે દોરી શકાય છે, અને કોલિન ડી વર્ડીયર મહત્તમ ચારમાં અપરિવર્તનશીલ છે. પ્રભાવ કોલિન ડી વર્ડીયર અપરિવર્તનને માત્ર એક મેટ્રિક્સને બદલે ગ્રાફને અનુરૂપ મેટ્રિક્સના વર્ગ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. સમાન રેખાઓ સાથે અન્ય આલેખ પરિમાણોને સમાન રેખાઓ સાથે વ્યાખ્યાયિત અને અભ્યાસ કરી શકાય છે, જેમ કે લઘુત્તમ ક્રમ, લઘુત્તમ અર્ધ-મર્યાદિત ક્રમ અને લઘુત્તમ વક્ર ક્રમ. નોંધો સંદર્ભો. નીલ જે. કાલ્કિન દ્વારા અનુવાદિત. . . . આલેખ અપરિવર્તન આલેખ લઘુ સિદ્ધાંત