Matematika | Diszkrét Matematika » Dr. Turjányi Sándor - Kombinatorika és gráfelmélet

Dr Turjányi Sándor Kombinatorika és Gráfelmélet 1998. Gráfelméleti alapfogalmak Minden józan ítéletû ember elôtt ismeretes, hogy QpKiQ pY yWD PiU HONH]G{G|WW D] tUiV PDJDU QHOYHQ LV amelyet nekünk Cicero és minden mûveltebb nemzet példája DODSMiQV~ORVRNRNEyOQDSUyOQDSUDPLQGMREEDQpVMREEDQ tôlünk telhetôleg mûvelni és gazdagítani kell. %RUQHPLV]D 3pWHUhGY|]OHWDQiMDVROYDVyQDN 9DQ DNL D JUiIHOPpOHW NH]GHWpW UH GDWiOMD PLNRU LV (XOHU PHJROGRWWD D .|QLJVEHUJLKLGDN SUREOpPiMiW 9DQ DNL .LUFKRII HOHNWURPRV KiOy]DWRNUD YRQDWNR]y EHQ SXEOLNiOW HUHGPpQHLKH] NDSFVROMD D JUiIHOPpOHW NH]GHWpW 0iVRN &DOHQHN HJ EHQ PHJMHOHQW FLNNpW WHNLQWLN D] HOV{ JUiIHOPpOHWL WDQXOPiQQDNPHOHWHJV]HUYHVNpPLDLDONDOPD]iV PRWLYiOW 6 WHUPpV]HWHVHQRODQRNLVYDQQDNDNLN*XWKULHQHN N|UO H 0RUJDQKR]LQWp]HWWNpUGpVpW{OV]iPtWMiNDJUiIHOPpOHWNH]GHWpW

$QHYH]HWHVNpUGpVDQpJV]tQVHMWpVNRUDL PHJIRJDOPD]iVD YROW 0LQGHQHVHWUHWDOiQHOIRJDGKDWyiOOiVSRQWD]KRJ D JUiIHOPpOHW YDODKROYDODPLNRUPHJV]OHWHWWpVD]XWyEELpYEHQHJUHW|EE KHOHQ DONDOPD]]iN RSHUiFLy NXWDWiVEDQ HOHNWURPRV KiOy]DWRN WHUYH]pVpEHQV]iPtWiVWHFQLNiEDQ $ JUiIRNDW QpPLOHJ SRQWDWODQXO ~J LV V]RNWiN MHOOHPH]QL PLQW SRQWRN pV YRQDODN KDOPD]iW (POpNH]YH D JUiIHOPpOHW JHRPHWULDL WRSROyJLDL LQGtWDWiViUD NH]GHWpUH 0L LWW D WiUJDOiV HOHMpQ LJHNV]QN WLV]WiQ D KDOPD]HOPpOHW QHOYpQ GHILQLiOQL D OHJW|EE JUiIHOPpOHWL DODSIRJDOPDW 7HUPpV]HWHVHQ QHP PRQGXQN OH DUUyO D OHKHW{VpJU{O VHP KRJ IHOKDV]QiOMXN D PDWHPDWLND PiV WHUOHWpQ HOpUW HUHGPpQHNHW PRQGDQGyQN MREE PHJYLOiJtWiVDpUGHNpEHQ HILQtFLy /HJHQ DGRWW D] ( pV 9 GLV]MXQNW KDOPD]RN pV OHJHQ DGRWW D] ( KDOPD]QDN D 9[9EH  9 |QPDJiYDO YHWW GLUHNW V]RU]DWiED  YDOy ϕ OHNpSH]pVH HNNRU D * (ϕ9 W LUiQ WRWW

JUiIQDNQHYH]]N $] ( KDOPD] HOHPHLW * (ϕ9  JUiI pOHLQHN pV D 9 KDOPD] HOHPHLWDJUiIFV~FVSRQWMDLQDNPRQGMXN+D e ∈ E é s ϕ (e) = (v1 , v2 ) DKRO v1 , v2 ∈V  DNNRU H]W ~J PRQGMXN KRJ D] H pO Y FV~FV SRQWEyO NLIXW  NLPHJ  V D Y FV~FVSRQWED PHJ YEH IXW  $ ϕ OHNpSH]pVW D JUiI LOOHV]NHGpVL OHNpSH]pVpQHN PRQGMXN $  WRYiEELDNEDQ YDODPHO $ KDOPD] V]iPRVViJiQDN D MHO|OpVpUH D] A V]LPEyOXPRW KDV]QiOMXN ,WW MHJH]]N PHJ KRJ H WiUJRQ EHOO NLYpWHOHV HVHWHNW{O HOWHNLQWYH PDMGQHP PLQGLJ YpJHV KDOPD]RNNDO IRJODONR]XQN D]D] D KDOPD]DLQN HOHPHLQHN D V]iPD YDODPHO QHP QHJDWtYHJpV]$* (ϕ9 JUiIRWYpJHVQHNPRQGMXNKDD](pVD 9 KDOPD]RN YpJHV KDOPD]RN D]D] E , V < ∞  $ WRYiEELDNEDQ KD FVDN D]HOOHQNH]{MpWQHPPRQGMXNPLQGLJYpJHVJUiIRNUyOEHV]pOQN KD HILQtFLy $ G = ( E , ϕ ,V )  UpV]JUiIMiQDN QHYH]]N D G = ( E , ϕ ,V )  L  E ⊆ E ,V ⊆ V pV L  (∀e

∈ E ) ⇒ (ϕ (e) = ϕ (e)) IHOWpWHOHNWHOMHVHGQHN $ IHQWL GHILQtFLyW V]HPOpOHWHVHQ ~J LV PHJIRJDOPD]KDWMXN KRJ D * JUiI EiUPHO  UpV]JUiIMiW PHJNDSKDWMXN RO PyGRQ KRJ * EL]RQRV pOHLW  W|U|OMN pV XJDQFVDN W|U|OKHWMN YDODPHO FV~FVDLW LV $ FV~FVRN W|UOpVpQpO D]RQEDQ JHOQQN NHOO DUUD KRJ D] DGRWW FV~FVUD LOOHV]NHG{ YDODPHQQL pOW LV W|U|OMN Lokális tulajdonságok HILQtFLy $ * (ϕ9  LUiQ WRWW JUiI v ∈V  FV~FViQDN NL IRNiQ D v  FV~FVEyO NLIXWy pOHN V]iPiW pUWMN pV δ ki (v ) YHO MHO|OMN HILQtFLy $  LUiQ WRWW JUiI v ∈V  FV~FViQDN EH IRNiQ D v FV~FVEDEHIXWypOHNV]iPiWpUWMNpV δ be (v ) YHOMHO|OMN ,7pWHO+D* (ϕ9 YpJHVJUiIDNNRU ∑ δ (v ) = ∑ δ (v ) = ki be v ∈V v ∈V E %L]RQ WiV $] pOHN V]iPD V]HULQWL WHOMHV LQGXNFLyYDO EL]RQ WXQN +D D * JUiIQDN QLQFV pOH DNNRU D ∑ δ ki (v );∑ δ be (v ); E v ∈V v ∈V

V]iPRNUHQGUHQXOOiYDOHJHQO{HNVtJDWpWHOiOOtWiVDQLOYiQ WHOMHVO 7pWHOH]]N IHO KRJ D WpWHO LJD] EiUPHO RODQ * JUiIUD DPHOQHN D] pOHLQHN D V]iPD Q YDJ NLVHEE PLQW Q ,JD]ROMXN D] iOOtWiVW D]RQ * JUiIRNUD DPHOHNQHN SRQWRVDQ Q pOH YDQ /HJHQ PRVW DGRWW * (ϕ9  pV E = n + 1 WRYiEEi OHJHQ RODQ G = ( E , ϕ ,V )  UpV]JUiIMD *QHN PHOUH E = n  pV 9 9 WHOMHVHGLN PiV V]yYDO * W  YDODPHO H pOpQHN D W|UOpVpYHO NDSWXN$]LQGXNFLyVIHOWHYpVV]HULQW ∑ δ (v ) = ∑ δ (v) = ki v ∈V be v ∈V E    $]RQEDQ D * (ϕ9  YpJHV JUiI ϕ LOOHV]NHGpVL OHNpSH]pVH EiUPHO e ∈ E élhez egyértelmûen hozzárendel egy (v1 , v 2 )  UHQGH]HWW SiUW DKRO v1  D NL IRNRN v2  D EH IRNRN D] H pO SHGLJ D] pOHN V]iPiW Q|YHOL HJHOHJHO 7HKiW KD  KH] W DGXQN DNNRU SRQWDEL]RQ WDQGy ∑ δ ki (v ) = ∑ δ be (v ) = E HJHQO{VpJDGyGLN v ∈V v ∈V HILQtFLy +D D] H pO

XJDQDEED D SRQWED PHJ YLVV]D DPHOE{O NLIXWRWW DNNRU KXURNpOQHN PRQGMXN D]D] ϕ (e) = (v1 , v 2 ) é s v1 = v 2  HILQtFLy+DD]HHpOHNUH ϕ (e1 ) = (v1 , v 2 ) pV ϕ (e2 ) = (v1 , v 2 ) DNNRU D]HHpOHNHWV]LJRU~DQSiUKX]DPRVDNQDNPRQGMXN HILQtFLy+DD]HHpOHNUH ϕ (e1 ) = (v1 , v 2 ) pV ϕ (e2 ) = (v 2 , v1 ) DNNRU D]HHpOHNHWSiUKX]DPRVRNQDNPRQGMXN HILQtFLy$9KDOPD]|QPDJiYDOYHWWUHQGH]HWOHQV]RU]DWiQ D]W D KDOPD]W pUWMN PHOQHN D] HOHPHL (vi , v j )  DODN~ UHQGH]HWOHQ SiURN-HOH9UQ9 HILQtFLy/HJHQDGRWWD](pV9KDOPD]pVOHJHQDGRWWD] (KDOPD]QDND9UQ9EH 9|QPDJiYDOYHWWUHQGH]HWOHQV]RU]DWiED YDOyϕOHNpSH]pVHHNNRUD* (ϕ9 WJUiIQDNQHYH]]N +D D * JUiI QHP LUiQ WRWW JUiI DNNRU QLQFV pUWHOPH szigorúan párhuzamos élekrôl beszélni. egyszerûen párhuzamos élt HVHWOHJ W|EEV]|U|V pOW PRQGXQN 1LOYiQ D KXURN pO IRJDOPD LUiQ WRWW pV LUiQ WDWODQ JUiI HVHWpQ XJDQD] +D YDODPHO *

JUiIEDQQLQFVVHPSiUKX]DPRVVHPKXURNpODNNRUD]WD*JUiIRW egyszerû gráfQDN QHYH]]N$ .HGYHV 2OYDVy WDOiONR]KDW RODQ N|QYHNNHO LV DPHOEHQ D]RQ * JUiIRNDW PHOHNEHQ SiUKX]DPRV pOHNLVWDOiOKDWyNPXOWLJUiIRNQDNQHYH]LN+DYDODPHOJUiIQDN HJHWOHQpOHVLQFVV]RNiVD]WUHVJUiIQDNPRQGDQL HILQtFLy $ * JUiI Y FV~FViQDN IRNiQ D YUH LOOHV]NHG{ pOHNV]iPiWpUWMN-HOH δ (v )  ,7pWHO  Np]IRJiVL WpWHO DNNRU ∑ δ (v ) = 2 E   +D D G ( E , ϕ ,V )  JUiI YpJHV v ∈V 7HNLQWVQN HJ WiUVDViJRW DKRO D] HPEHUHN QHP FVDN V]yED iOOQDNHJPiVVDOGHRONRURONRUPpJNH]HWLVIRJQDNV{WD]W VHP]iUMXNNLKRJHJHVHNW|EEV]|ULVNH]HWIRJWDNYDJYDODNL |QPDJiYDOIRJRWWNH]HW+DPRVWD]HPEHUHNHWWHNLQWMNDJUiIXQN FV~FVSRQWMDLQDN pV HJHJ Np]IRJiVW HJ pOQHN DNNRU D WpWHO SRQWRVDQ D]W iOOtWMD KRJ D Np]IRJiVRN V]iPD EiUPHO  WiUVDViJEDQ SiURV )pOUHpUWpVHN HONHUOpVH YpJHWW KD ; NH]HW IRJRWW <DO 

DNNRU < LV NH]HW IRJRWW ;HO  PiV V]yYDO D Np]IRJiVRN HJHQUDQJ~DN  $ WpWHO V]LJRU~ EL]RQ WiVD D] , WpWHOEL]RQ WiViKR]KDVRQOyDQW|UWpQKHW+DYDODPHOFV~FVSRQW IRNDDNNRUD]WDSRQWRWL]ROiOWSRQWQDNQHYH]]N .|YHWNH]PpQ $ * JUiI SiUDWODQ IRN~ FV~FVDLQDN D V]iPD SiURV 9DOyEDQD ∑ δ (v ) |VV]HJHWIHOOHKHWERQWDQLNpWUpV]UHNO|Q v ∈V gyûjtve ∑ δ (v) = v ∈V a páros ∑ δ (v ) + v ∈V ,δ ( v ) ≡ 0 mod ( 2 ) és a ∑ δ (v) = 2 E   páratlan fokú csúcsokat azaz v ∈V ,δ ( v ) ≡1 mod ( 2 )  E{OOiWKDWyKRJD ∑ δ (v ) V]iPSiURV v ∈V ,δ ( v ) ≡1 mod ( 2 )  V PLYHO SiUDWODQ VRN SiUDWODQ V]iP |VV]HJH SiUDWODQ H]pUWD ∑ δ (v ) WDJMDLQDNDV]iPDFVDNSiURVOHKHW v ∈V ,δ ( v ) ≡1 mod ( 2 ) Utak, körök, fák  +R]]RQ D I|OG VDUMDW PDJWHUP{ IYHW JP|OFVIiW*HQH]LV%UpVLWK, HILQLFLy $ G = ( E , ϕ ,V )  JUiI e1 , e2 ,., ek  pOVRUR]DWRW W|U|WW YRQDOnak (

vagy egyszerûen csak YRQDOQDN HVHWOHJ VpWiQDN PRQGMXNKD ϕ (e1 ) = (v 0 , v1 ), ϕ (e2 ) = (v1 , v 2 ),., ϕ (ek ) = (v k −1 , v k )  HILQLFLy $] e1 , e2 ,., ek  W|U|WW YRQDODW ~WQDN PRQGMXN KD D v0 , v1 , v2 ,., vk −1 , vk FV~FVRNSiURQNpQWNO|QE|]{HN $ IHQWL GHILQLFLyW ~J LV PHJIRJDOPD]KDWMXN NLFVLW V]HPOpOHWHVHEEHQ  KRJ D * JUiI Y FV~FViEyO ~W PHJ YNED YDJ D] ~W RODQ Q OW W|U|WW YRQDO PHO VHKROVHP PHWV]L |QPDJiW HILQLFLy  $] e1 , e2 ,., ek  W|U|WW YRQDODW N|UQHN FLNOXVQDN PRQGMXNKDD v1 , v2 ,., vk −1 , vk FV~FVRNSiURQNpQWNO|QE|]{HNGHv0 = vk  HILQtFLy $ G( E ,ϕ ,V )  JUiI XY FV~FVSRQWMDLQDN D G XY WiYROViJiQ az õket összekötõ legrövidebb út hosszát értjük. Ha a NpW SRQWRW QHP N|WL |VV]H ~W DNNRU D NpW SRQW WiYROViJiW YpJWHOHQQHN∞WHNLQWMN  HILQtFLy $ G( E ,ϕ ,V )  JUiI SRQWMDL N|]|WWL WiYROViJ PD[LPXPiW D *  gráf átmérõMpQHN QHYH]]N DPLW

GLDP YHO d (u, v )  MHO|OQN GLDP(*((ϕ  9)) = max u ,v ∈V 7pWHO +D D * (ϕ,V) gráf összefüggõ, akkor a csúcspontok halmaza metrikus tér az elõbb értelmezett távolság fogalomra Qp]YH %L]RQ WiV Az összefüggõség miatt d(u,v)∈5 pV G XY  DNNRU pV FVDN DNNRUKDX Y 0LYHO LUiQ WDWODQ JUiIUyO EHV]pOQN QLOYiQ WHOMHVO D V]LPPHWULDLVD]D]G XY G YX  A háromszög egyenlõség azért teljesedik, mert az u,v pontokat összekötõ utak legrövidebbikénél nem lehet rövidebb RODQ~WDPHOQpOPpJSOXV]N|YHWHOPpQWLVV]DEXQNWXGQLLOOLN D]W KRJ PpJ HJ WRYiEEL SRQWRW ZW LV WDUWDOPD]D d (u, v ) ≤ d (u, w) + d (w, v )  HILQLFLy $ G = ( E , ϕ ,V )  JUiIRW |VV]HIJJ{QHN PRQGMXN KD EiUPHOFV~FViEyOYLV]EiUPHOPiVLNFV~FViED~W HILQLFLy $ * JUiIQDN D  UpV]JUiIMiW NRPSRQHQVQHN QHYH]]NKDUHQGHONH]LNDN|YHWNH]{WXODMGRQViJRNNDO L * |VV]HIJJ{ LL  QHP OpWH]LN *QHN RODQ  |VV]HIJJ{ UpV]JUiIMD PHO*

WYDOyGLPyGRQWDUWDOPD]]D 5|YLGHQ IRJDOPD]KDWXQN YROQD ~J LV KRJ * |VV]HIJJ{ PD[LPiOLVUpV]JUiIMDLW*NRPSRQHQVHLQHNQHYH]]N HILQLFLy: A G egyszerû gráfot |VV]HIJJ{pVQHPWDUWDOPD]N|UW IiQDN  PRQGMXN KD ,7pWHO %iUPHO * ID WDUWDOPD] OHJDOiEE HJ HOV{IRN~ FV~FVRW %L]RQ WiV ,QGLUHNW EL]RQ WXQN 7HJN IHO KRJ D] iOOtWiV QHP LJD] D] QLOYiQ DQQLW MHOHQW KRJ * EiUPHO FV~FViQDN D IRND QpO QDJREE YDJ HJHQO{ QHP OHKHW D] |VV]HIJJ{VpJ PLDWW ,QGXOMXQN HO * YDODPHO Y FV~FViEyO Y EyO YH]HVVHQ H pO YEH YE{O H pO YEH pV tJ WRYiEE YN E{O HN YNED  (O{EE YDJ XWyEE YLVV]D pUNH]QN HJ RODQ YM FV~FVED VLWWDN|U DKROPiUNRUiEEDQMiUWXQNPLYHO*QHN YpJHV VRN FV~FVD YDQ pV LQGLUHNW IHOWHYpVQN V]HULQW PLQGHJLN FV~FViQDN D IRND OHJDOiEE NHWW{ YROW $]D] KD EHpUNH]WQN  YDODPHO FV~FVED HJ H pOOHO DNNRU HJ PiVLN H  pOOHO RQQDQ WRYD LV

WXGWXQN EDOOyNi]QL 6 YpJO OiWWXN KRJ D] HM HMHN W|U|WWYRQDO HJ N|UH D * JUiIQDN HOOHQWpWEHQ D]]DO KRJ * ID YROW V D]  HOOHQWPRQGiV RND QLOYiQ D] LQGLUHNW IHOWHYpVQNYDOD HILQtFLy$*JUiIRWHUGnekPRQGMXNKDNRPSRQHVHLIiN ,7pWHO+D*JUiIIDDNNRU V − 1 = E  %L]RQ WiV $ * ID pOHLQHN V]iPD V]HULQWL WHOMHV LQGXNFLyYDOEL]RQ WXN+DD*QHNHJpOHYDQDNNRUD]iOOtWiV LJD]7pWHOH]]NIHOKRJEiUPHORODQIiUDLJD]D]iOOtWiV PHOQHNOHJIHOMHEEQpOHYDQ/HJHQPRVWD G = ( E , ϕ ,V ) IDJUiIQDN QpOHD]D] E = n + 1*HJpOpWW|U|OYH G1 = ( E1 , ϕ 1 ,V1 ) pV G2 = ( E 2 , ϕ 2 ,V2 ) NRPSRQHQVHNUH HVLN V]pW pV QLOYiQ PLQGNHWW{ ID PHOUH PiU D] LQGXNFLyV IHOWHYpV PLDWW LJD] D] iOOtWiV 7HKiW pUYpQHV V1 − 1 = E1  V2 − 1 = E2  H NpW XWyEEL HJHQOHWHW |VV]HDGYD V1 + V2 − 2 = E1 + E2  DGyGLN )LJHOHPEH YpYH KRJ V1 + V2 = V  WRYiEEi E1 + E2 + 1 = E . Látható hogy az n+1 élû

gráfra is teljesül az iOOtWiV ,7pWHO +D D G = ( E , ϕ ,V )  JUiI HUG{ pV N NRPSRQHQVE{O iOO DNNRU V − k = E  %L]RQ WiV $ IHOWpWHO V]HULQW D G = ( E , ϕ ,V )  JUiI D G1 = ( E1 , ϕ 1 ,V1 )  G2 = ( E 2 , ϕ 2 ,V2 )  Gk = ( E k , ϕ k ,Vk )  NRPSRQHVHNE{O iOO PHOHNUH UHQGUH WHOMHVO KRJ V1 − 1 = E1 , V2 − 1 = E2 ,., Vk − 1 = E k  ( N GDUDE HJHQOHW PHJIHOHO{ ROGDODLW |VV]HDGYD DGyGLN D WpWHO iOOtWiVD $] , WpWHOEHQ PHJIRJDOPD]WXN KRJ HJ G = ( E , ϕ ,V ) IDJUiIQDN OHJDOiEE HJ HOV{IRN~  SO v1 ∈V , δ (v1 ) = 1 FV~FVD YDQ ( WpWHOW PRVW N|QQHQ SRQWRVtWKDWMXN RODQ IRUPiQ KRJ HJ IDJUiIQDN OHJDOiEE NpW HOV{IRN~ SRQWMD YDQ 9DOyEDQ D] , WpWHO V]HULQW D JUiI IRNDLQDN |VV]HJH SiURV D]D] D] HO{EE HPOtWHWW HOV{IRN~ FV~FVRQ NtYO WDUWDOPD] PpJ OHJDOiEE HJ v 2 ∈V , δ (v 2 ) = 1 mod(2) YDJ W|EE SiUDWODQ IRN~ FV~FVRW $] ( ) |VV]HIJJ{VpJ PLDWW 2 ≤ δ (v 3 ),2 ≤ δ (v

4 ),.,2 ≤ δ v V  WRYiEEEi δ (v1 ) = 1, 3 ≤ δ (v 2 )  $] HO{EEL HJHQO{VpJHNNHO DOXOUyO EHFVOYH * IRNDLQDN |VV]HJpW ∑ δ (v ) ≥ 2 V DGyGLNDPLHOOHQWPRQGD],WpWHOQHN v ∈V 7pWHO%iUPHOIDJUiIQDNOHJDOiEEHOV{IRN~SRQWMDYDQ  9HJJNpV]UHKRJH]XWyEELiOOtWiVQHPMDYtWKDWyYDJLV YDQ RODQ ID DPHOQHN SRQWRVDQ  HOV{IRN~ SRQWMD YDQ 6]HPOpOWHWKHWQN HJ RODQ JUiIRW PHOQHN FVXSiQ NpW HOV{IRN~ SRQWMDYDQHJIRQDOODOPHOQHNNpWYpJpUHFVRPyWN|WW|WQNV N|]EOV{KHOHNHQN|W|WWQNDIRQiOUD V − 2 FVRPyW$FVRPyNDWD JUiI FV~FVDLQDN pV NpW V]RPV]pGRV FVRPyW N|]YHWOHQO |VV]HN|W{ FVRPy PHQWHV  IRQDO GDUDERW pOQHN WHNLQWQN $ PiVLN V]pOV{VpJHV  IiW V]HPOpOWHVVN HJ WDUDMRVVOOHO $ ID pOHLQHN D WDUDMRVVO WVNpLW WHNLQWVN FV~FVSRQWRNQDN SHGLJ HJUpV]WDWDUDMRVVOWLOOHWYHDWVNpNV]DEDGRQPDUDGWYpJpW $IiQDNHNNRUYDQHJSRQWMDPHOQHNDIRNDNVD]|VV]HV W|EELFV~FVIRND

HILQLFLy$ G = ( E , ϕ ,V ) JUiID G1 = ( E1 , ϕ 1 ,V1 ) JUiIIDOL]RPRUIKD WHOMHVHGQHNDN|YHWNH]{IHOWpWHOHN (i) létezik kölcsönösen egyértelmû αOHNpSH]pVH(QHN(UH (ii)létezik kölcsönösen egyértelmû βOHNpSH]pVH9QHN9UH  LLL   ∀e ∈ E , ha ϕ (e) = v i , v j   (    ⇒ ϕ 1 (α (e)) = (β (v1 ), β (v 2 ))   ) ( ) *UiIRN L]RPRUILiMD NO|QE|]LN D WRSROyJLD KRPHRPRUILD IRJDOPiWyO 7HNLQWVQN SpOGiXO D]W D * JUiIRW  DPHO NpW SRQWEyO V D] D]RNUD LOOHV]NHG{ KXURNpOE{O iOO 5HDOL]iOMD *W NpW |VV]HNDSFVROW NXOFVWDUWy NDULND KD V]pW NDSFVROMXN D NpW NDULNiW DNNRU D NDSRWW *  JUiI L]RPRUI HOGH WRSROyJLDL pUWHOHPEHQ*QHPHNYLYDOHQV YHOHILQtFLy$ = ((  ϕ9 ) JUiI IHV]tW{IiMiQDN PRQGMXN D * W KD UpV]JUiIMD QHN pV  ID PiVUpV]W*PLQGHQFV~FVD QHLVFV~FVD 7pWHO$*JUiIQDNDNNRUpVFVDNDNNRUYDQIHV]tW{IiMDKD *|VV]HIJJ{ %L]RQ WiV

/HJHQ * |VV]HIJJ{ PXWDVVXN PHJ KRJ HNNRU OpWH]LN IHV]tW{IiMD +D * QHP WDUWDOPD] N|UW DNNRU  D] |VV]HIJJ{VpJPLDWWIDpV|QPDJiQDNIHV]tW{IiMD+D*WDUWDOPD] N|UWDNNRUDN|UYDODPHOHpOpWW|U|OYH*E{O JUiIRWNDSXQN DPHO  WRYiEEUD LV |VV]HIJJ{ PDUDG +D * QH YDQ N|UH  DNNRU LVPpWHOKDJXQNHJH pOWD* JUiIEyO9pJHVVRNOpSpVHQEHOO HOMXWXQN HJ RODQ  JUiIKR] PHO PpJ |VV]HIJJ{ GH PiU QLQFV N|UHH]D* N JUiIMyIHV]tW{IiMiQDN $] iOOtWiV PHJIRUGtWiVD WULYLiOLV PLYHO D IDJUiI |VV]HIJJ{ 6 D] LV HOpJ PDJiWyO pUWHW{G{ KRJ KD D * JUiIQDN YDQ|VV]HIJJ{UpV]JUiIMDDNNRU*LV|VV]HIJJ{  6RNHVHWEHQEL]RQXOKDV]QRVQDND]LUiQ WRWWIDIRJDOPD$ * LUiQ WRWW JUiIEDQ D] H H  H  pO VRUR]DW KD ϕ (H ) = (Y   Y ) ϕ (H  ) = (Y  Y  ) ϕ (H ) = (Y −   Y )   pV Y ≠ Y  KD L ≠ M  $ * JUiIQDN N N N N L M

YDODPHOYFV~FVDJ|NHUHKD*EiUPHOYW{ONO|QE|]{FV~FViED HO OHKHW MXWQL LUiQ WRWW ~WWDO $ * JUiI LUiQ WRWW ID KD LUiQ WiV QpONO WHNLQWYH ID pV YDQ HJ Y J|NHUH PHOE{O EiUPHOFV~FViEDYH]HWLUiQ WRWW~W Teljes gráf, komplementer gráf HILQLFLy $ G = ( E , ϕ ,V )  JUiIRW Q V]|JSRQW~ WHOMHV JUiIQDN QHYH]]NKDEiUPHONpWNO|QE|]{FV~FViWpON|WL|VV]HEiUPHO PiVLNFV~FFVDOpV V = n -HOH.Q 7pWHO$.QQSRQW~WHOMHVJUiIpOHLQHNDV]iPD n(n − 1) 2  %L]RQLWiV $ .Q GHILQLFL{MD V]HULQW EiUPHO V]|JSRQW IRND Q $ JUiIXQNQDN |VV]HVHQ Q FV~FVSRQMD YDQ  H]pUW D JUiI FF~SRQWMDL IRNDLQDN D] |VV]HJH SRQWRVDQ Q Q  $] , WpWHO V]HULQWHNNRUDJUiIpOHLQHNDV]iPDSRQWRVDQ /HJHQ DGRWW D * = ((  ϕ9 )  pV 9 = Q egyszerû gráf, s legyen KQ QHN D * = ((  ϕ 9 )  RODQ UpV]JUiIMD PHO  = ((  ϕ9 ) YHO L]RPRUI 7|U|OMN .QQHN * = ((  ϕ 9 ) K|] WDUWR]y pOHLW $ NDSRWW JUiI OHV] *

NRPSOHPHQWHUH 0iV PHJIRJDOPD]iVEDQ = ((  ϕ 9 )  NRPSOHPHQWHUH D * = ((  ϕ9 )  JUiIQDN KD = ((  ϕ 9 )  pOHL WHOMHV JUiIIi HJpV]tWLN NL *W 1LOYiQ D WHOMHV JUiI NRPSOHPHQWHUH D] UHV JUiI pV IRUGtWYD D] UHV JUiI NRPSOHPHQWHUH D WHOMHV JUiI $] Q V]|JSRQW~WHOMHVJUiIRWOHKHW~JWHNLQWHQLPLQWD]QFV~FVSRQW~ QGLPHQ]LyVV]LPSOH[JUiIMiW )HODGDWRN  5DM]ROMRQ RODQ  FV~FVSRQW~ JUiIRNDW PHOHNQHN  KDUPDGIRN~ pV  QHJHGIRN~ SRQWMD YDQ +iQ pOH YDQ D UDM]ROW JUiIRNQDN"  +iQ RODQ  FV~FVSRQW~ JUiI YDQ DKRO D FV~FVRN IRNDL UHQGUH   (J WiUVDViJ WDJMDL Np]IRJiVVDO GY|]OLN HJPiVW %L]RQ WVD EH KRJ SiURV D]RQ HPEHUHN V]iPD DNLN SiUDWODQ VRNV]RUIRJWDNNH]HW %L]RQ WVDEHKRJKDD G( E , ϕ ,V ) egyszerû gráfnak 2 vagy NHWW{QpO W|EE FV~FVD YDQ (V ≥ 2)  DNNRU YDQ NpW D]RQRV IRNV]iP~ FV~FVD (JVDNNYHUVHQHQEiUPHOMiWpNRVMiWV]LNEiUPHOPiVLN

MiWpNRVVDO EL]RQ WVD EH KRJ D YHUVHQ EiUPHO V]DNDV]iEDQ YDQ NpW RODQ YHUVHQ]{ DNLN DGGLJ D]RQRV V]iP~ PpUN{]pVW MiWV]RWWDN 6. Hány olyan 5 pontú ( nem izomorf ) egyszerû gráf van, PHOUHWHOMHVHGLNKRJEiUPHOSRQWMiQDNDIRNDOHJDOiEE %L]RQ WVDEHKRJKDD*|VV]HIJJ{JUiIFV~FVDLQDND V]iPD n ≥ 2 pVpOHLQHNDV]iPDQQpONHYHVHEEDNNRUYDQHOV{IRN~ FV~FVDLV  %L]RQ WVD EH KRJ KD Q V]iP~ WHOHIRQN|]SRQW N|]O EiUPHO NHWW{ N|]|WW OpWHVtWKHW{ |VV]HN|WWHWpV DNNRU YDQ OHJDOiEEQV]iP~N|]YHWOHQ|VV]HN|WWHWpVLV +DHJQSRQW~JUiIPLQGHQSRQWMiQDNDIRNDOHJDOiEEQ DNNRUDJUiI|VV]HIJJ{  %L]RQ WVD EH KD D * JUiI PLQGHQ SRQWMiQDN DIRND OHJDOiEENHWW{DNNRUYDQN|UH  (J VDNN FVDSDW EDMQRNViJUD Q FVDSDW QHYH]HWW EH V HGGLJ Q PpUN{]pVW MiWV]RWWDN OH 0XWDVVD PHJ KRJ YDQ N|]|WWN OHJDOiEE HJ FVDSDW PHO OHJDOiEE  PpUN{]pVW PiU OHMiWV]RWW  %L]RQ WVD EH KRJ D *

|VV]HIJJ{ JUiI YDODPHO pOpW W|U|OYHXMEyO|VV]HIJJ{JUiIRWNDSXQN 13. Bizonyítsa be, hogy az n pontú, n élû egyszerû gráfnak YDQOHJDOiEEHJN|UH  %L]RQ WVD EH KRJ D G( E , ϕ ,V ) összefüggô egyszerû gráf DNNRU pV FVDN DNNRU PDUDG |VV]HIJJ{ HJ e ∈ E  pOpQHN W|UOpVH XWiQKDYDQ*QHNRODQNN|UHPHOWDUWDOPD]]DHW 15. Bizonyítsa be, hogy az összefüggô egyszerû véges gráf pOHLQHN D KDOPD]D DNNRU pV FVDN DNNRU DONRW N|UW KD * YDODPHQQLIRND 0HOLND]DOHJQDJREESHJpV]V]iPDPHOUHDTFV~FV~ WHOMHVJUiISV]HUHVHQ|VV]HIJJ{  17. Mutassa meg, hogy ha egy teljes egyszerû gráf éleihez EiUKRJDQ LV LUiQ WiVW tUXQN HO{ DNNRU D] HUHGPpQO NDSRWW írányított gráfnak szükségszerûen létezik irányított feszítô IiMD  /HJHQ δ 0 (G( E , ϕ ,V )) = min (δ (v )) ≥ v ∈V V −1 2 ,s G egyszerû gráf. %L]RQ WVDKRJ*|VV]HIJJ{,JD]OHV]HD]HO{EELiOOtWiVKD  V − 1 

WHOMHVODKROD>[@IJJYpQD]  2  FVDND δ 0 (G( E , ϕ ,V )) = min (δ (v )) ≥  v ∈V [HJpV]UpV]pWMHO|OL  0XWDVVD PHJ KRJ HJ Q FV~FV~ pV N |VV]HIJJ{ NRPSRQHQVE{OiOOyJUiIEDQD]pOHNV]iPDOHJIHOMHEE (n − k )(n − k + 1) 1 2 OHKHW 20.Bizonyítsa be, hogy egy összefüggô egyszerû gráfban EiUPHO NpW PD[LPiOLV KRVV]~ViJ~ ~WQDN YDQ OHJDOiEE HJ N|]|V FV~FVD  $] DOiEEL *  JUiIRN N|]O PHOHN L]RPRUIDN PHOHN QHP" 22.Határozza meg a kocka gráfjának az átmérõjét   +DWiUR]]D PHJ D] Q GLPHQ]LyV NRFND pV D] Q GLPHQ]LyV szimplex átmérõjét. 24. Határozza meg azon G gráfok átmérõinek a maximumát illetve minimumát, amelyek összefüggõek és csúcspontjaik száma n. Adjom meg olyan gráfokat, melyek átmérõje megegyezik az elõbb HPOtWHWPD[LPXPPDOLOOHWYHPLQLPXPPDO  3HUPXWiFLyNYDULiFLyNNRPELQiFLyNLVPpWOpVVHOpVLVPpWOpVQpONO HILQtFLy $] Q NO|QE|]{

HOHP HJ SHUPXWiFLyMiQ  Q HOHP  HJ U|J]tWHWWVRUUHQGMpWpUWMN 3pOGiXO Q  HVHWpQ OHJHQ  D V]yEDQ IRUJy HOHPHN V D] DGRWW VRUUHQGMN  $ SHUPXWiFLyW OHKHW ~J LV GHILQLiOQL PLQW egy n elemû halmaz önmagára való kölcsönösen egyértelmû leképezését. Az  1 2 3 4 5 6 HO{EEL SHUPXWiFLyW HNNRU PHJ OHKHW DGQL D]    DODNEDQ H] D]  3 2 4 1 5 6  x  DODN D IJJYpQHN WiEOi]DWWDO YDOy PHJDGiViQDN HJ W|P|U MHO|OpVH    f ( x ) $ IHOV{ VRUEDQ IJJHWOHQ YiOWR]y pUWpNHL D] DOVy VRUEDQ D IJJ{ YiOWR]y PHJIHOHO{ pUWpNHL V]HUHSHOQHN Q IDNWRULiOLVQDN PRQGMXN D] HJPiVXWiQ N|YHWNH]{ Q V]iPRN V]RU]DWiW MHOH Q ⋅⋅ Q ⋅Q pV   PHJiOODSRGiVV]HULQW 3Q Q 7pWHO Az n elemû H halmaz összes különbözô permutációinak a száma %L]RQ WiV$+KDOPD]HOHPHLQHNDV]iPDV]HULQWLWHOMHVLQGXNFLyYDO EL]RQ WXQN Q  HVHWpQ D] iOOtWiV

LJD] PHUW HJ HOHPHW FVDN HJIpOHNpSSHQ OHKHW VRUED iOOtWDQL 7pWHOH]]N IHO KRJ D] iOOtWiV LJD] QUH V PXWDVVXN PHJ H IHOWHYpVE{O N|YHWNH]LN  KRJ LJD] Q UH LV /HJHQPHJDGYDD+KDOPD]HOHPHLQHNHJU|J]tWHWWVRUUHQGMHSO (h1 , h2 ,., hn )  %iUPHOLNSHUPXWiFLyQiOD"MHOOHOMHO|OWKHOHN (? h1 ,? h2 ,.,? hn ?) YDODPHOLNpUH EHV]~UKDWMXN D KQW /iWKDWy KRJ D] Q HOHP EiUPHO SHUPXWiFLyMiEyO (n+1) darab különbözô (n+1) elemû permutációt lehet legyártani, tehát Q  H]pUW D EiUPHO QUH WHOMHVO D] (h1 , h 2 , . , h n )  V PLYHO Q Q EL]RQ WiVVDONpV]YDJXQN HILQtFLy/HJHQDGRWWQHOHPPHOHNN|]O l1 , l2 ,., lk UHQGUH HJIRUPD  pV l1 + l2 +. + lk = n   H]HQ HOHPHN HJ U|J]tWHWW VRUUHQGMpW HJ LVPpWOpVHV SHUPXWiFLyQDNQHYH]]N 3pOGiXO KD HJ RV]WiO WDQXOyLW D GROJR]DWXNUD NDSRWW MHJHN DODSMiQVRUUHQGEHiOOtWMXNDNNRUD]HJIRUPDMHJHWNDSRWWWDQXOyNN|]|WW PiUQHPWHV]QNNO|QEVpJHW

7pWHO +D D] Q HOHP N|]O l1 , l2 ,., lk  l1 + l2 +. + lk = n DNNRULVPpWOpVHVSHUPXWiFLyLQDNDV]iPD Pn,l1 ,l2 ,.,lk UHQGUH HJIRUPD pV n!  l1 ! l2 !. lk ! %L]RQ WiV /HJHQ PHJDGYD D (h1 , h2 ,., hn )  HOHPHNQHN YDODPHO LVPpWOpVHV SHUPXWiFLyMD $ SHUPXWiFLyEDQ OpY{ HJIRUPD HOHPHNHW NO|QE|]WHVVN PHJ LQGH[HNNHO pV SHUPXWiOMXN D] HGGLJ D]RQRVQDN WHNLQWHWW HOHPHNHW LV ^3pOGiXO HJ  I{V RV]WiOEDQ  |W|VW pV  QpJHVW DGWXQN pV D  GROJR]DWRNDW   VRUED RV]WRWWXN NL LQGH[HOYH D] HGGLJ HJIRUPiQDN WHNLQWHWW MHJHNHW (51 ,41 , 4 2 ,52 ,53 )  ( SHUPXWiFLyEyO  LVPpWOpV QpONOL SHUPXWiFLy DGyGLN` (JHWOHQ HJ LVPpWOpVHV SHUPXWiFLyEyO l1 ! l2 !. lk ! V]iP~ LVPpWOpV QpONOL SHUPXWiFLyW NDSXQN H]pUW Pn ,l1 ,l2 ,.,lk l1 ! l2 ! lk ! Q V LQQHQ PiUYDOyEDQl1 ! l2 !. lk !YHOYDOyRV]WiVXWiQDGyGLNDWpWHOiOOtWiVD HILQtFLy Q NO|QE|]{ HOHP N|]O NLYiODV]WRWW UHQGH]HWW N HOHPHW

LVPpWOpVQpONOLNDGRV]WiO~YDULiFLyQDNQHYH]]N 3pOGiXO KD HJ IXWy YHUVHQHQ K~V]DQ LQGXOWDN pV D] HOV{  EHIXWyW GtMD]WiN DNNRU D GtMD]RWWDNDW WHNLQWKHWMN  HOHP  KDUPDG RV]WiO~ YDULiFLyMiQDN n k V 7pWHO Q HOHP LVPpWOpV QpONOL NDG RV]WiO~ YDULiFLyLQDN D V]iPD Q Q  Q N  %L]RQ WiV 5|J]tWHWW Q PHOOHWW N V]HULQWL WHOMHV LQGXNFLyYDO EL]RQ WXQN N UH D] iOOtWiV LJD] PLYHO Q HOHPE{O W SRQWRVDQ Q IpOHNpSSHQ OHKHW NLYiODV]WDQL 7pWHOH]]N IHO KRJ NUD WHOMHVHGLN pV LJD]ROMXN N UH %iUPHOLN (h1 , h2 ,., hk )  NDG RV]WiO~ YDULiFLyKR] QN HOHP N|]O YiODV]WKDWXQN HJ KNW KRJ HJ (h1 , h2 ,., hk , hk +1 )  N HG RV]WiO~ YDULiFLyW NDSMXQN $]D] LJD] D N|YHWNH]{ |VV]HIJJpV Vkn (n − k ) = Vkn+1 PLiOWDOWpWHOQNEL]RQ WiVWQHUW HILQtFLyQNO|QE|]{HOHPE{OKDNHOHPHWROPyGRQYiODV]WXQNNL KRJ HJ HOHPHW W|EEV]|U LV YiODV]WKDWXQN pV D VRUUHQG V]iPtW DNNRU Q

HOHPNDGRV]WiO~LVPpWOpVHVYDULiFLyMiUyOEHV]pOQN 3pOGiXO KD YDODNL NLW|OW HJ WL]HQQpJ PpUN{]pVHV WRWy V]HOYpQW DNNRUD][HOHPHNQHNPHJDGWDHJHGRV]WiO~YDULiFLyMiW 7pWHOQNO|QE|]{HOHP|VV]HVNDGRV]WiO~LVPpWOpVHVYDULiFLyLQDN DV]iPDVkn,ism = n k  %L]RQ WiV -HO|OMH QQ D] Q NO|QE|]{ HOHPHW H]HQ elemek közül k-t egymásután leírva egy legfeljebb k jegyû számot kapunk az QDODS~V]iPUHQGV]HUEHQPHOHNQHNDV]iPDQLOYiQn k VH]]HODEL]RQ WiV NpV] 7HNLQWKHWMN D] Q NO|QE|]{ HOHP HJ NDG RV]WiO~ LVPpWOpVHVH variációját úgy is mint az n elemû H halmaz önmagával vett k-szoros direkt V]RU]DWiQDN HJ HOHPpW V DNNRU D] LV HOpJ QLOYiQYDOy KRJ N + ⊗ + ⊗ ⊗ + = +  ,WW H  MHO|OL D + KDOPD] HOHPHLQHN D V]iPiW 9HJN   N észre azt is, hogy az n elemû H halmaz k szoros direkt szorzatának a (h KKN HOHPpWWHNLQWKHWMNROPyGRQLVPLQWD]. ^N`KDOPD]RQ

pUWHOPH]HWW I IJJYpQW PHOQHN D] pUWpNHL UHQGUH K K KN (NNRU D K-n értelmezett H-beli értékeket felvevõ különbözõ függvények száma nN *RQGROMD YpJLJ D .HGYHV 2OYDVy KRJ D Q pUWHOPH]HWW +EpOL pUWpNHNHW felvevõ injektív függvények száma Vkn Q Q  Q N  HILQtFLyQNO|QE|]{HOHPN|]ONLYiODV]WYDNHOHPHWPHOHNQpOD UHQGH]pVUH QHP YDJXQN WHNLQWHWWHO D] Q HOHP HJ NDG RV]WiO~ NRPELQiFLyMiWNDSMXN  3pOGiXO KD YDODNL D] |W|V ORWWyQ KHOHVHQ NLW|OW HJ V]HOYpQW DNNRU D  HOHPQHN PHJDGWD HJ |G RV]WiO~ NRPELQiFLyMiW ÈOODSRGMXQN  n  n n!  V]iPRW    V]RNiV ELQRPLiOLV PHJ DEEDQ KRJ    IRJMD MHO|OQL D  k  k (n − k )! k ! HJWWKDWyQDNLVQHYH]QL  n 7pWHOQHOHPNDGRV]WiO~NRPELQiFLyLQDNDV]iPDCkn     k %L]RQ WiV Q HOHP YDODPHO LVPpWOpV QpONOL NDG RV]WiO~

NRPELQiFLyMiEyONV]iP~NDGRV]WiO~LVPpWOpVQpONOLYDULiFLyQHUKHW{ KD D] HOHPHNHW HJPiV N|]|WW SHUPXWiOMXN 7HKiW IHQQiOO D N|YHWNH]{ n! Ckn N Vkn  )LJHOHPEH YpYH KRJ Vkn = n(n − 1).(n − (k − 1)) =  NDSMXN D WpWHO (n − k )! iOOtWiViW HILQtFLy +D D] Q HOHP N|]O RO PyGRQ YiODV]WXQN NL N GDUDERW KRJ HJ HOHP W|EEV]|U LV V]HUHSHOKHW pV D VRUUHQGUH QHP YDJXQN WHNLQWHWWHO DNNRU D] Q HOHP HJ LVPpWOpVHV NDG RV]WiO~ NRPELQiFLyMiUyO EHV]pOQN Ckn,ism. 7pWHO Q HOHP NDG RV]WiO~ LVPpWOpVHV NRPELQiFLyLQDN D V]iPD  n + k − 1 =  k   %L]RQ WiV $ EL]RQ WiV DODS|WOHWH U|YLGHQ FVXSiQ DQQL KRJ megadunk egy kölcsönösen egyértelmû leképezést (n+k-1) különbözô elem k-ad RV]WiO~ LVPpWOpV QpONOL NRPELQiFLyL pV Q NO|QE|]{ HOHP NDG RV]WiO~ LVPpWOpVHVNRPELQiFLyLN|]|WW/HJHQD]QNO|QE|]{HOHPQHJpV D] QN  NO|QE|]{ HOHP QQQN  $]

Q NO|QE|]{ HOHP HJ LVPpWOpVHV NDGRV]WiO~ NRPELQiFLyMD QDJViJ V]HULQW VRUED UHQGH]YH OHJHQ 0 ≤ α1 ≤ α 2 ≤. ≤ α k ≤ n  $] (α 1 ,α 2 ,.,α k )  LVPpWOpVHV NRPELQiFLyQDN IHOHOWHVVN PHJ D] (α 1 ,α 2 + 1,α 3 + 2,.,α k + k − 1)  HOHPHN LVPpWOpV QpONOL N DGRV]WiO~ NRPELQiFLyMiW /iWKDWy KRJ 0 ≤ α1 < α 2 + 1 <. < α k + k − 1 ≤ n + k − 1  H]pUW D] (α 1 ,α 2 + 1,α 3 + 2,.,α k + k − 1)  HOHPHN YDOyEDQ D] QN NO|QE|]{ HOHP ismétlés nélküli kombinációja, s az összeadás egyértelmûsége miatt a leképezés kölcsönösen egyértelmû volta is garantált. %LQRPLiOLVpVSROLQRPLiOLVWpWHO 7pWHO SROLQRPLiOLV /HJHQ ∀a1 , a2 ,., a k ∈ R , ahol R kommutatív gyûrû pVQHJQpOQDJREEWHUPpV]HWHVV]iPHNNRU (a1 + a2 +.ak )n = n! a1s1 a2s2 . aksk  s ! s !. s ! s1 + s2 + . + s k = n 1 2 k ∑ %L]RQ WiV Tudjuk, hogy bármely kommutatív gyûrûben a több tag

V]RU]iViWW|EEWDJJDOROPyGRQYpJH]KHWMNHOKRJPLQGHQWDJRWV]RU]XQN PLQGHQWDJJDO+DIHOtUMXND]QWpQH]{V  (a1 + a2 +.+ak )(a1 + a2 ++ak ) (a1 + a2 ++ak ) V]RU]DWRW  n DNNRUD] a1 elemet s1 − szer az n zá rójelbôl     s1  n − s1 a2 elemet s2 − szer az n − s1 zá rójelbôl     s2   n − s1 − s2 −.− sk −1  ak elemet sk − szor az n − s1 − s2 −.− sk −1 zá rójelbôl   sk   OHKHWNLYiODV]WDQL$] IpOHNpSSHQ  n   n − s1  n − s1 − s2 −.− sk −1     .   sk  s1  s2    n! (n − s1 )! . (n − s1 − s2 −− sk −1 )! n!  (n − s1 )! s1! (n − s1 − s2 )! s2 ! (n − s1 − s2 −.− sk )! sk ! s1 ! s2 ! sk ! 6 H] XWyEEL HJHQO{VpJ MREEROGDOiQ D WpWHOEHQ V]HUHSO{ a1s1 a2s2 . a ksk  WDJ HJWWKDWyMDiOODPLYHOiOOtWiVXQNDWEL]RQ WRWWXNLV 7pWHO  ELQRPLiOLV WpWHO  /HJHQ ∀a1 , a2 , ∈ R , ahol

R kommutatív gyûrû pVQHJQpOQDJREEWHUPpV]HWHVV]iPHNNRU (a1 + a2 ) = n s1 = n  n ∑  s  a s1 = 0 s1 1 a2n − s1  1 %L]RQ WiV .|YHWNH]PpQ $ WpWHO D SROLQRPLiOLV WpWHO VSHFLiOLV HVHWH  n  n  n  n   n n  +   +   +.+  +  = 2  ∗  0  1  2  n − 1  n (1 + 1)n =   n  n  n n −1  n  n  n  −   +   −.+(−1)   + (−1)   = 0  ∗∗  0  1  2  n − 1  n (1 − 1)n =  6]LWDIRUPXOD $ V]LWD IRUPXOD D] HUDWRV]WKHQpV]L V]LWD OHV]iUPD]RWWMD DEEDQ D] pUWHOHPEHQ KRJ D] HUDWRV]WKHQpV]L V]LWD PyGV]HUW DGRWW D]RQ N V]iPRN PHJKDWiUR]iViUD PHOHN SUtPV]iPRN HJ HO{UH PHJDGRWW YpJHV KDOPD]iQDN HJLN HOHPpYHO VHP RV]WKDWyN $ V]LWD IRUPXOD NpSOHWHW DG D + KDOPD]D]RQHOHPHLQHNDV]iPiUDPHOHNQHPHOHPHL+HO{UHDGRWW H1 , H2 ,.,

Hn UpV]KDOPD]DLHJLNpQHNVHP 7pWHO V]LWDIRUPXOD  /HJHQ DGRWW D + YpJHV KDOPD] pV H1 , H2 ,., Hn UpV]KDOPD]DLHNNRU  + ∪ + ∪+  = + − + − + − − + + + ∩ + + + ∩ + + + + ∩ + + Q   + + ∩ + + + +  (−)       ∩ + − + ∩ + ∩ + − − + − Q  Q + ∩ + ∩ + ∩∩+ Q Q      Q = + + ∑ (−) Q − ∑ V = ∩+  %L]RQ WiV ,VPHUW KRJ + ∪ + ∪∪+   Q  ∩ + + + − Q  Q + ∩ + ∩∩+  L ≤ L < L < < LV ≤ Q V   Q  L LV  = + − + ∪ + ∪∪+  H]pUW D Q  Q  EL]RQ WDQGyHJHQO{VpJHNYLYDOHQVD]DOiEELYDO + ∪ + ∪ + ∪∪+    Q = ∑ (−) Q ∑ − V  = + ∩ + ∩∩+ L ≤ L < L < < LV ≤ Q V    L LV ∗  (] XWyEEL IRUPXOD EL]RQ WiViW Q V]HULQWL WHOMHV LQGXNFLyYDO YpJH]]N Q UH D] iOOtWiV QLOYiQYDOyDQ LJD] Q  HVHWpQ + ∪ + = −

+ + − + + − + ∩ + WHOMHVOPHUWDPHWV]HW HOHPHLW GXSOiQ          V]iPROWXN 7pWHOH]]N IHO KRJ D IRUPXOD LJD] KD Q ≥ ,JD]ROMXN D] iOOtWiVW QUH $ [+  ∪ +  ∪ +  ∪  ∪+ Q− ] ∪ + Q = +  ∪ +  ∪ +  ∪  ∪+ Q− + + Q − (+  ∪ +  ∪ +  ∪  ∪+ Q− ) ∩ + Q IRUPXODD] Q  VSHFLiOLV HVHW DONDOPD]iViYDO NDSKDWy PHJ -REE ROGDOiQDN XWROVy WDJMiUDDONDOPD]YDDGLV]WULEXWLYLWiVWDGyGLND]DOiEELFpOMDLQNQDNMREEDQ PHJIHOHO{ IRUPXOD [+  ∪ +  ∪ +  ∪  ∪+ Q− ] ∪ + Q = + ∪ +  ∪ +  ∪  ∪+ Q− + + Q − (+ ∩ + Q ) ∪ (+  ∩ + Q ∪  ∪(+ Q− ∩ + Q )) L $] L  MREE ROGDOiQ V]HUHSO{ HOV{ WDJUD DONDOPD]YD D] LQGXNFLyV IHOWHYpVWtUKDWMXNKRJ − Q  + ∪ + ∪ + ∪∪+   − Q   = ∑ (−) = V   Q ∪ + ∩ + ∪∪ + Q  − Q  + ∩ + ∩∩+ ≤ L < L < < LV ≤ Q −  SHGLJDN|YHWNH]{W +

∩+ ∑ − V   ∩+ L L − Q  Q = ∑ (−) − V  =  Q ∪ + ∩ + ∪∪ + Q  Q − ∩+  Q Q = ∑ (−) V = ∑ + ∩ + ∩∩+ ∩ + LOO ∑ + ∩ + ∩∩+ ≤ L < L < < LV ≤ Q − V  + ∩+ LL DKDUPDGLNWDJUD LV   − V  ≤ L ≤ L ≤ ≤ LV ≤ Q −   L L LV Q  L L LV LLL  $] L  IRUPXOiED YLVV]D tUYD LL  pV LLL W  SRQWRVDQ D EL]RQ WDQGy ∗ IRUPXOiWNDSMXNVH]]HODEL]RQ WiVNpV] +D .|YHWNH]PpQ ,  (i1 ,i2 ,.,is ) ( ) EiUPHO ill. i , i ,, i HVHWpQ + ∩ + ∩∩+ , 1 , 2 , s L L LV VUH  pV WHWV]{OHJHV = + ∩ + ∩∩+ DNNRU L   L    LV  Q + ∪ + ∪∪+ = + + ∑ (−)   + ∩ + ∩∩+   V = Q V   Q   V V   .|YHWNH]PpQ ,, /HJHQ$N$QHlemû halmaz , ekkor a AW$EH n s  n k NpSH]{V]UMHNWtYOHNpSH]pVHN IJJYpQHN V]iPD n k + ∑

(−1)   (n − s)   s s =1 %L]RQ WiV $] ,  N|YHWNH]PpQW DONDOPD]]XN DUUD D] HVHWUH KD +L MHO|OL D]RNDW D] $W $UH NpSH]{ IJJYpQHNHW PHOHNQpO D] $ DL HOHPH QHPOpSIHONpSNpQW 0HJMHJ]pV $ V]LWD IRUPXOiQDN D V]iPHOPpOHWEHQ YDQQDN NLIHMH]HWWHQ ILQRP pV UHQGNLYO PpO DONDOPD]iVDL .RPELQDWRULNiEDQ D V]LWD V]pS iOWDOiQRVtWiVDN|V]|QKHW{*&5RWDQDN 3HUPXWiFLyNV]LPPHWULNXVFVRSRUW )JJYpQHN N|UpEHQ LVPHUW D] |VV]HWHWW IJJYpQ  NpS]pV mûvelete, ennek megfelelôen értelmezhetünk a permutációk között is egy mûveletet, a permutációk szorzását, mint a megfelelô leképezések HJPiVXWiQYpJUHKDMWiViW3pOGD  1 2 3 4 5 6  1 2 3 4 5 6      6 3 4 1 2 5  2 1 4 3 6 5  1 2 3 4 5 6    3 6 1 4 5 2 MREEUyOEDOUD  V]RUR]WXQN DQQDN PHJIHOHO{HQ KRJ KD D] ,WW I J  |VV]HWHWW IJJYpQ D]W MHOHQWL KRJ HO{V]|U YpJUHKDMWMXN JW PDMG

IW3HUV]HD]HO{EELV]RU]iVWHOYpJH]KHWMN  1 2 3 4 5 6  1 2 3 4 5 6      6 3 4 1 2 5  2 1 4 3 6 5  1 2 3 4 5 6    5 4 3 2 1 6 EDOUyOMREEUD  LV  D] HUHGPpQ SHUV]H iOWDOiEDQ PiV OHV] NLYpYH KD D NpW HOHP IHOFVHUpOKHW{   DOJHEUDL V]HPSRQWEyO D]RQEDQ ugyanaz az algebrai struktúra adódik mindkét esetben, célszerû adott WpPDN|U|QEHOO D]RQEDQ FVDN D] HJLN tUiVPyGRW KDV]QiOQL 0L D] XWyEEL D EDOUyOMREEUD tUiVPyGKtYHLYDJXQN 7pWHO Az n elemû H halmaz permutációi a permutációk szorzására Qp]YH FVRSRUWRW DONRWQDN -HOH 6Q D 6 D V]LPPHWULiUD XWDO D FVRSRUW V]RNiVRVQHYHDV]LPPHWULNXVFVRSRUW %L]RQ WiV,JD]ROMXNVRUEDQKRJWHOMHVHGQHNDFVRSRUWD[LyPiN L  $ SHUPXWiFLyN V]RU]iVD két változós algebrai mûvelet PHUW D + önmagára való kölcsönösen egyértelmû leképezéseinek egymásutánja is, H önmagára való kölcsönösen egyértelmû leképezése. LL

 $] DVV]RFLDWtYLWiV LV WHOMHVO PLYHO OHNpSH]pVHN V]RU]iVD PLQGLJDVV]RFLDWtY LLL /pWH]LNHJVpJHOHPWLD]LGHQWLNXVOHNpSH]pV LY  0LQGHQ HOHPQHN YDQ LQYHU]H is, mivel a kölcsönösen egyértelmû OHNpSH]pVHNLQYHUWiOKDWyN  HILQtFLy$]WDSHUPXWiFLyWPHOEHQNpWHOHPFVHUpOWFVXSiQKHOHW  1 2 . i j n WUDQV]SR]LFLyQDN QHYH]]N 3pOGiXO $]    SHUPXWiFLy D] L  1 2 . j i n MHOHPHNQHNHJWUDQV]SR]LFLyMD %iUPHO WUDQV]SR]LFLyW IHOtUKDWXQN V]RPV]pGRV WUDQV]SR]LFLyN  1,2,., i ,, j ,, n V]RU]DWDNpQW $] LGHQWLNXV SHUPXWiFLyEyO   E{O ( M − L)  GDUDE  1,2,., i ,, j ,, n V]RPV]pGRV HOHPQHN D WUDQV]SR]LFLyMiYDO FVHUpMpYHO  NDSMXN D . j − 1 j n  1 2 . i    SHUPXWiFLyW V H] XWyEEL SHUPXWiFLyEyO i − j − 1 j i. n  1 2 . i + 1 b g  1 2 . i j n V]RPV]pGRV HOHP FVHUpYHO DGyGLN D    SHUPXWiFLy D]D] D]  1 2 . j i n LGHQWLNXVSHUPXWiFLyEyO (2(i − j )

− 1) V]RPV]pGRVHOHPQHNDFVHUpMpYHOPHJNDSMXN D]LWMYHOIHOFVHUpO{WUDQV]SR]LFLyW HILQtFLy 2 1  α 1 α 2 . i . α i . j . α j $] αi , α j  HOHPHN LQYHU]LyEDQ YDQQDN D] . n   SHUPXWiFLyEDQKD α j < α i  .α n  HILQtFLy 9DODPHO SHUPXWiFLyW DV]HULQW PRQGXQN SiURVQDN LOO SiUDWODQQDN  KRJ D SHUPXWiFLyEDQ OpY{ LQYHU]LyN V]iPD SiURV YDJ SiUDWODQ $] HGGLJLHN DODSMiQ QLOYiQYDOy KRJ V]RPV]pGRV HOHPHN FVHUpMHNRU D SHUPXWiFLyEDQ OpY{ LQYHU]LyN V]iPD YDJ HO Q{ YDJ HJJHO FV|NNHQ 6 PLYHO EiUPHO WUDQV]SR]LFy D] LGHQWLNXV SHUPXWiFLyEyO SiUDWODQ VRN V]RPV]pGRV HOHP FVHUpMpYHO PHJNDSKDWy H]pUW EiUPHO WUDQV]SR]LFLy SiUDWODQSHUPXWiFLy 7pWHO V]RU]DWDNpQW %iUPHO SHUPXWiFLy HO{iOO YpJHV VRN WUDQV]SR]LFLy %L]RQ WiV +D DGRWW YpJHV VRN HOHPQHN HJ U|J]tWHWW VRUUHQGMH DNNRU HOHPHNQHN SiURQNpQWL IHOFVHUpOpVpYHO HOMXWKDWXQN EiUPHO PiV HO{UH U|J]tWHWW VRUUHQGKH] LV

$] HOHPHNQHN D V]iPD V]HULQW EL]RQ WKDWXQN Q Q UH D] iOOtWiV WULYLiOLV 7HJN IHO KRJ D] iOOtWiV LJD] Q≥ UH pV EL]RQ WVXN QUH $] LQGXNFLyV IHOWHYpV V]HULQW HOpUKHW{ WUDQV]SR]LFLyNNDO KRJ D] HOV{ Q HOHP D KHOpQ OHJHQ KD D] XWROVy NHWW{ QHP D KHOpQ iOO  DNNRU PHJFVHUpOYH {NHW NpV] YDJXQN D EL]RQ WiVVDO .|YHWNH]PpQ $ SiURV SHUPXWiFLyN D V]RU]iVUD Qp]YH FVRSRUWRW DONRWQDN $SiURVpVDSiUDWODQSHUPXWiFLyNV]iPDPHJHJH]LNKDn ≥ 2  $]QHOHP|VV]HVSHUPXWiFLyLQDNDFVRSRUWMiWW|EEIpOHPyGRQLVOHKHW UHSUH]HQWiOQL /HJHQ DGRWW D] Q GLPHQ]LyV WpUEHQ HJ V]DEiORV Q FV~FVSRQW~ 6=Q V]LPSOH[ $] 6=Q V]LPSOH[ |QPDJiUD YDOy WiYROViJWDUWy KRPRJpQ OLQHiULV OHNpSH]pVHLQHN D FVRSRUWMD SRQWRVDQ D] Q HOHP V]LPPHWULDFVRSRUWMiYDOHJH]LNPHJ  7HNLQWVN D]RNDW D] E 1 2 . i  α α 2 . α i  1 . j . α j . n   . α n   Q Q HV PiWUL[RNDW DPHOHN D] Q Q

 ( HJVpJ PiWUL[EyO ~J NHOHWNH]QHN KRJ D] LLN RV]ORSED( α i LNHOHPHNHUO$] E 1 2 . i j n  PiWUL[RNDV]RNiVRV   α 1 α 2 . α i . α j  . α n  V]RU]iVUD Qp]YH FVRSRUWRW DONRWQDN V H FVRSRUW L]RPRUI D] Q  HOHP V]LPPHWULDFVRSRUWMiYDO )HODGDWRN  $] $ YiURVEyO % YiURVED  RQQDQ &EH  ~W YH]HW +iQIpOHNpSSHQ OHKHWHOMXWQL$EyO&EH%QNHUHV]WO"  .pW YpJYiUQDN   NDWRQiMD YDQ   NDWRQiW NLiOOtWDQDN SiUYLDGDOUD+iQIpOHNpSSHQYiODV]WKDWQDNNLHJSiUW"  (J KHJ FV~FViUD  ~W YH]HW (J WXULVWD IHOPHJ YDODPHO ~WRQ PDMGOHM|QHJPiVLNRQ+iQIpOH~WYRQDON|]|WWYiODV]WKDWRWW" $VDNNWiEOiQKiQIpOHNpSSHQYiODV]WKDWXQNNL L HJIHKpUpVHJIHNHWHPH]{W LL  HJ IHKpU pV HJ IHNHWH PH]{W RO PyGRQ KRJ NO|QE|]{ VRUED pVNO|QE|]{RV]ORSEDOHJHQHN"  +DW Ki]DVSiU N|]O KiQIpOHNpSSHQ OHKHW NLYiODV]WDQL HJ IpUILW

pVHJQ{WKRJDNpWNLYiODV]WRWWQHPKi]DVSiU" (JNRViUEDQDOPDLOO EDUDFN YDQ -XOLVND NLYHV]  DOPiW YDJ HJ EDUDFNRW -XOLVND XWiQ -DQFVL YiODV]W HJ DOPiW pV HJ EDUDFNRW LV0LNRUYDQ-DQFVLQDNW|EEYiODV]WiVLOHKHW{VpJHKD-XOLVNDDOPiWYDJ KDEDUDFNRWYHWW"  -DQFVLND pV -XOLVND YLUiJRW V]HGWHN D] HUG{EHQ  KyYLUiJRW  LEROiW pV  JyODKtUW +D]DIHOp PHQYpQ HORV]WRWWiN D YLUiJRW HJPiV N|]|WWKiQIpOHNpSSHQWHKHWWpNPHJD]W"  $] $ LOO % YiURVRNDW  I{~WYRQDO N|WL |VV]H pV D]RNDW  másodrendû útvonal keresztezi. Hányféle úton lehet eljutni A-ból B-be, IHOWpYHKRJHJ~WRQOHJIHOMHEEHJV]HUPHJQNYpJLJ"  $] $EyO LQGXOy YRQDWRQ Q XWDV YDQ V %LJ P PHJiOOy OHJNpV{EE %EHQPLQGHQNLNLV]iOO+iQIpOHNpSSHQW|UWpQKHWH]"  eUWHOPH]]H D] HO{EEL IHODGDWRW RO PyGRQ KRJ D] XWDVRNDW HJIRUPiQDNWHNLQWLVYiODV]ROMDPHJD]RWWIHOWHWWNpUGpVW"  7L]HQpJ

GLiN DQDOt]LVE{O YL]VJi]RWW 6]i] ÈUSiG 7DQiU ÒUQiO KiQIpOH HUHGPpQH OHKHW D YL]VJiQDN KD D]QDS FVDN  DV MHJHN V]OHWWHN"  +iQ SR]LWtY RV]WyMD YDQ D] Q HJpV] V]iP KD Q p α  LOO D] Q Sα  Sα   SNα " N  $]  ODSRV IUDQFLD NiUWiEyO DW RV]WyQDN  HPEHUQHN KiQIpOHNpSSHQOHKHWVpJH VH]"  +iQIpOHNpSSHQ OHKHW D  ODSRV PDJDU NiUWiEyO W NLYiODV]WDQLROPyGRQKRJPLQGDV]tQV]HUHSHOMHQOHJDOiEEHJV]HU"   -y]VLNiQDN  EDUiWMD YDQ  DONDORPPDO PHJKtY N|]ON KiUPDW +iQIpOHNpSSHQWHKHWLH]WPHJ~JKRJXJDQD]DWiUVDViJQHM|MM|Q|VV]H NpWV]HU"  5DM]ROMRQ  RODQ WpJODODSRW PHOHN ROGDODLQDN D KRVV]DL D] V]iPRNN|]ONHUOQHNNLPpJKR]]i~JKRJPLQGHJLN SRQWRVDQ HJV]HU OpS IHO  KD D WpJODODSRN HJIRUPD ROGDODLW HJV]HUHV PXOWLSOLFLWiVVDO V]iPROMXN  V D] |W WpJODODS PHJIHOHO{ PyGRQ HJPiV

PHOOpKHOH]YHHJ~MDEEWpJODODSRWDONRW 17. Hány négyjegyû ill ötjegyû számot írhatunk SiUDWODQV]iPMHJVHJtWVpJpYHORVV]iPUHQGV]HUEHQ fel 5 ill. 6. 18. Hány olyan ötjegyû szám van a tízes számrendszerben, melyben L DQHPIRUGXOHO{ LL OHJDOiEEHJSiURVV]iPMHJHWWDUWDOPD] LLL DpVDV]iPMHJHNHWWDUWDOPD]]D   HJiJDV V]iOORGDL V]REiED KiQIpOHNpSSHQ OHKHW HOKHOH]QL  WXULVWiW"  )HKpUIHNHWH ViUJD NpNSLURV pV ]|OG J|QJ|NE{O KiQIpOH  WDJ~ OiQFRW OHKHW FVLQiOQL" 0HQQL OHV] D]RQ OiQFRN V]iPD  DPHOHNEHQ legalább egy piros és legalább egy zöld színû gyöngy is van? 21. Piros,fehér,zöld és kék színû golyóink vannak 6 különbözô PpUHWEHQ 1pJ GRER]EDQ HOKHOH]QN KDWKDW JROyW JHOYH DUUD KRJ HJ dobozba különbözô méretû, de azonos színû golyók kerüljenek. Hányféle módon lehet 4 különbözô méretû és színû golyót kiválasztani a dobozokból. 22. Határozza meg a

hétjegyû számok közül azoknak a számát, amelyek L FVDNSiUDWODQ LL FVDNSiURV LLL SiURVpVSiUDWODQ LY SiURVpVSiUDWODQV]iPMHJHWWDUWDOPD]QDN $ODSRVPDJDUNiUWiEyOODSRWK~]XQN+iQIpOHNpSSHQOHKHW D]iV]NLUiOIHOV{DOVyWt]HVNLOHQFHVQROFDVVRUUHQGHWNLK~]QL  (J WiUVDViJEDQ  IpUIL pV  Q{ YDQ +iQIpOHNpSSHQ OHKHW {NHW HJNHUHNDV]WDON|Up~JOHOWHWQLKRJQHOM|QNpWQ{HJPiVPHOOHWW" 25. PHOHNEHQ Határozza meg azoknak az ötjegyû számoknak az összegét, L OHJIHOMHEED]V]iPMHJHNV]HUHSHOQHN LL D]V]iPRNOHJIHOMHEEHJV]HUIRUGXOQDNHO{ LLL OHJIHOMHEEDV]iPMHJHNiOOKDWQDN LY PHOHNQHNPLQGHQMHJHNO|QE|]{  +iURP IpUIL pV KiURP Q{L PDQ|NHQW KiQIpOHNpSSHQ OHKHW RO PyGRQ VRUED iOOtWDQL KRJ VHP NpW Q{ VHP NpW IpUIL QHP iOOKDW HJPiV PHOOHWW"   P IpUIL pV Q Q{ N|]O NW NLYiODV]WDQDN PLQGHJLN NLYiODV]WRWW PiVPiV

DMiQGpNRW NDS  +iQ RODQ HVHW OHV] DPLNRU D NLYiODV]WRWWDN N|]|WWSRQWRVDQOK|OJOHV]" 28. Adott a síkon n darab általános helyzetû egyenes ( nincs N|]|WWN  SiUKX]DPRV pV VHPHOLN KiURP QHP LOOHV]NHGLN HJ SRQWUD  +iQ WDUWRPiQUDERQWMiNDVtNRW" 29. Adott a 3 dimenziós euklideszi térben n általános helyzetû sík ( VHPHOLN NHWW{ QHP SiUKX]DPRV VHPHOLN KiURP QHP LOOHV]NHGLN HJ HJHQHVUH VHPHOLN QpJQHN QLQFV HJ N|]|V SRQWMD  +iQ UpV]UH ERQWMiN DWHUHW"  Q NO|QE|]{ WpQH]{E{O iOOy V]RU]DWRW KiQIpOHNpSSHQ OHKHW NpWNpWWpQH]{E{OiOOyWpQH]{NV]RU]DWiUDERQWDQL +iQIpOHNpSSHQOHKHW|WGREyNRFNiYDODWGREQL" +iQIpOHNpSSHQOHKHWKiURPGREyNRFNiYDOHWGREQL"  +iQIpOHNpSSHQ KHOH]KHWQN HO HJ  SROFRV V]HNUpQEH  N|QYHWKDHJSROFRQHOIpUPLQGD"  (J Ki]DVSiU KDW ~UEyO pV KDW K|OJE{O iOOy WiUVDViJRW KtY YHQGpJVpJEH RO PyGRQ KRJ KDWDQ D IpUM pV KDWDQ D

IHOHVpJ LVPHU{VHL +iQIpOHNpSSHQWHKHWLNH]WKDDIpUMQHN|WQ{pVKpWIpUILD IHOHVpJQHN KpWQ{pV|WIpUILLVPHU{VHYDQ"  +yIHKpUNH OHYHOHW tUW D KpW W|USpQHN $ JRQRV] ERV]RUNiQ D]RQEDQ |VV]HFVHUpOWH D OHYHOHNHW RO JDOiGXO KRJ VHQNL VHP D VDMiWMiW NDSWD+iQIpOHNpSSHQWHKHWWHPHJD]WDJRQRV]ERV]RUND  +iURPIpOH WpPiUyO OHYHOH]  WXGyV %iUPHOLN WXGyV EiUPHOLN PiVLNNDO OHYHOH] GH FVDN HJ WpPiUyO %L]RQ WVD EH KRJ YDQ N|]|WWN OHJDOiEEWXGyVDNLNXJDQDUUyODWpPiUyOOHYHOH]QHNHJPiVVDO  n + m  n  m  n  m   n  m %L]RQ WVDEHKRJ   =    +    +.+       k   0  k   1  k − 1  k  0  +iQ V]yWiUW NHOO NLDGQL KRJ N|]YHWOHQO OHKHVVHQ IRUGtWDQL NO|QE|]{QHOYEiUPHOLNpU{OEiUPHOPiVLNUD" +iQUDYpJ]{GLND111000 − 1V]iP" ( )

+DWiUR]]DPHJD][RQHJWWKDWyMiWD] 1 + x 2 − x 3 SROLQRPEDQ 7 V]iPN|]OKiQRODQYDQDPHO L QHPRV]WKDWyVHPYHOVHPPDO LL QHPRV]WKDWyVHPYHOVHPPDOVHPWHO LY QHPRV]WKDWyVHPYHOVHPPDOVHPWHOVHPWHO" 42. Az n elemû halmaznak, hány lineáris rendezése van? (JFVRPDJPDJDUNiUWiEyOKiQIpOHNpSSHQOHKHWNLYiODV]WDQL (i) négy páronként különbözô színû lapot, (ii) négy páronként különbözô színû és értékû lapot, LLL QpJRODWPHOHNN|]ONHWW{NLUiO"   $] XOWLQiO KiQIpOH OHRV]WiV OHKHWVpJHV"  +iURP JHUPHN N|]|WW V]pWRV]WXQN  GDUDE  IRULQWRV pUPpW +iQIpOHNpSSHQ OHKHW PHJFVLQiOQL D] HORV]WiVW L KD D] LV HO{IRUGXOKDW KRJ YDODPHOLN JHUHN HJ pUPpW VHP NDS LL KD EiUPHOLN JHUPHN OHJDOiEE HJ pUPpW NDS LLL KD EiUPHOLN JHUPHN OHJDOiEE KiURP pUPpW NDS"  +iQIpOHNpSSHQ K~]KDW IHO YDODNL D] HJLN NH]pQHN XMMDLUD  NO|QE|]{ gyûrût, ha a hüvelykujjára nem húz

gyûrût és ha bármely másik ujjára fel fér mind D    OiQ N|]|WW  Uy]ViW  tULV]W  DPDULOOLV]W  WXOLSiQW pV HJ RUFKLGHiW RV]WRWWDN V]pW RO PyGRQ KRJ PLQGHJLNN HJHJ YLUiJRW NDSRWW 0HQQL D OHKHWVpJHV HORV]WiVRN V]iPD"  $ N|QYHVSROFRQ  N|QY YDQ +iQIpOHNpSSHQ OHKHW N|]ON NLYiODV]WDQL  RODW PHO QHP HJPiV PHOOHWW iOO"  /HJHQ D] Q V]iP NDQRQLNXV DODNMD NO|QE|]{ SR]LWtY RV]WyLQDN D] |VV]HJpW p1α1 p2α 2 . pkα k  +DWiUR]]D PHJ D] Q 50. Hány olyan "szó" készíthetô a felejthetetlen szóból, amelyben e betûk QLQFVHQHN HJPiV PHOOHWW"  +iQIpOHNpSSHQ ERQWKDWXQN IHO HJ Q WHUPpV]HWHV V]iPRW KiURP WHUPpV]HWHV V]iP |VV]HJpUH" $ VRUUHQGHW LV ILJHOHPEH YpYH  $GRWW D VtNRQ D] H LOO I SiUKX]DPRV HJHQHVHN HQ P GDUDE IHQ Q GDUDE NO|QE|]{ SRQW YDQ +iQ RODQ QHP HOIDMXOy KiURPV]|J YDQ D VtNRQ PHOQHN D FV~FVDL D] DGRWW SRQWRN N|]O NHUOQHN NL"  (J QpJ]HW PLQGHQ ROGDOiW Q HJHQO{ UpV]UH RV]WXQN +iQ RODQ

KiURPV]|J YDQ DPHOQHN FV~FVDL D] HO{EE HPOtWHWW RV]WySRQWRN N|]O NHUOQHN NL" $GRWW D VtNRQ Q GDUDE HJHQHV DPHOHN N|]O QLQFV KiURP  PHO HJ SRQWUD LOOHV]NHGQH pV EiUPHO NHWW{ PHWV]L HJPiVW +iQ PHWV]pVSRQWMD YDQ D] Q GDUDE HJHQHVQHN" $GRWW D VtNRQ Q GDUDE SRQW PHOHN N|]O VHPHOLN  QLQFV HJ HJHQHVHQ +iQ HJHQHVpW KDWiUR]]iN PHJ D] HO{EE HPOtWHWW SRQWRN D VtNQDN"  $GRWW D KiURPGLPHQ]LyV WpUEHQ Q SRQW PHOHN N|]O VHPHOLN KiURP QLQFV HJ HJHQHVHQ N|]ON P YLV]RQW HJ VtNEDQ KHOH]NHGLN HO D PHJPDUDGW QP SRQW N|]O PiU VHPHOLN QpJ QHP NRPSODQiULV +iQ VtN LOOHV]WKHW{ D] DGRWW Q SRQWUD"  +iQ RODQ KiURPV]|J YDQ PHOQHN FV~FVDL HJEHHVQHN HJ DGRWW NRQYH[ Q V]|J FV~FVDLYDO  GH QLQFV N|]|V ROGDOXN"  .RPELQDWRULNDL ~WRQ LJD]ROMD KRJ L LLL  n  n  n 3   + 6  + 6  = n  1  2  3 LL  n  n  n 3 1 + 7  + 12  + 6  = (n + 1)  1  2  3 

n  n  n 4 1 + 14  + 36  + 24  = (n + 1) − n 4  1  2  3  n  n  n  n LY    + 14  + 36  + 24  = n 4   1  2  3  4  (XOHUJUiIRN+DPLOWRQXWDNpV+DPLOWRQN|U|N /HRQDUG (XOHU   QHYpKH] NDSFVROyGLN D] HOV{ JUiIHOPpOHWL PXQND PHO EDQ MHOHQW PHJ D 6]HQWSpWHUYiUL 7XGRPiQRV $NDGpPLD N|]OHPpQHLEHQ $] pUWHNH]pVpW (XOHU D] ~Q .|QLJVEHUJL KLGDN SUREOpPiMiYDO NH]GWH $ 3UHJHO IROy $ % V]LJHWHLW KLGDN N|W|WWpN |VV]H HJPiVVDO pV D -REE SDUW SDUWRNNDO LV $] $ V]LJHWHW NpW SiUKX]DPRV KtG N|W|WWH |VV]H D MREE SDUWWDO HJ KtG D % $ % V]LJHWWHO V XJDQFVDN NpW SiUKX]DPRV KtG YH]HWHW D] $UyO D EDO SDUWUD LV %W HJHJ KtG N|W|WWH |VV]H D EDO pV D MREE SDUWWDO LV pV %U{O %DO SDUW YH]HWHW HJ KtG $ UD LV  PHOHW D] HO{EE PiU HPOtWHWWQN $ NpUGpV D] YROW EH OHKHW H

MiUQL D KLGDNDW YDODPHO IL[ & SRQWEyO RO PyGRQ KRJ PLQGHQ KtGRQ iWPHJQN SRQWRVDQ HJV]HU (XOHU OpQHJpEHQWHOMHViOWDOiQRVViJEDQPHJROGRWWDDIHODGDWRW HILQtFLy $ G = ( E , ϕ ,V )  JUiI / pOVRUR]DWiW ϕ (e1 ) = (v0 , v1 ), ϕ (e2 ) = (v1 , v2 ),., ϕ (en ) = (vn −1 , vn ) W ]iUW (XOHUYRQDOQDN QHYH]]N KD ( PLQGHQ pOpW SRQWRVDQ HJV]HU WDUWDOPD]]D pV v0 = vn   KD v0 ≠ vn  DNNRU /W Q OW(XOHUYRQDOQDNPRQGMXN +D YDODPHO JUiIQDN YDQ ]iUW (XOHUYRQDOD V]RNiV D]W (XOHUJUiI QpYYHO LOOHWQL 1LOYiQ HJ (XOHUJUiI |VV]HIJJ{ pV EiUPHO FV~FVSRQWMiQDN D IRND SiURV PLYHO KD D] (XOHUYRQDOD EHWpU YDODPHO FV~FVSRQWED PLQG DQQLV]RU NL LV PHJ RQQDQ 0HJMHJH]]N KRJ YDQ DNL (XOHUJUiIQDN QHYH] RODQ JUiIRW DPHOQHN EiUPHO FV~FVIRND SiURV $ N|YHWNH]{WpWHOOpQHJpEHQ(XOHUW{OV]iUPD]LN (  7pWHO $ * JUiI DNNRU pV FVDN DNNRU (XOHUJUiI KD |VV]HIJJ{ pVEiUPHOFV~FViQDNDIRNDSiURV

%L]RQ WiV $] KRJ HJ (XOHUJUiI V]NVpJNpSSHQ |VV]HIJJ{ pV PLQGHQ FV~FVSRQWMiQDN D IRND SiURV D] UHPpOKHW{HQ YLOiJRV D WpWHO HO{WWL VRURNEyO $ IHOWpWHO HOpJVpJHV YROWiKR] WHNLQWVN D * JUiI YDODPHO Y FV~FViW$]  H pO YH]HVVHQ YEyO YEH V YE{O H YEH pV tJ WRYiEE YpJO HN HOYLV] YN YED PHUW KD YDODPHO FV~FVSRQWED EHPHQWQN D FV~FVSRQW IRNiQDN SiURV YROWD PLDWW NL LV WXGWXQN M|QQL +D D NDSRWW / pOVRUR]DWWDUWDOPD]]DD*JUiIYDODPHQQLpOpWDNNRUNpV]YDJXQN+DQHP WDUWDOPD]]DSpOGiXOD]H pOWpVXXH]HQpONpWYpJSRQWMDDNNRUXE{O LQGXOYD D] HO{EELHNKH] KDVRQOyDQ WDOiOXQN HJ XJDQFVDN XEHQ YpJ]{G{ / ]iUW YRQDODW +D X D] / ]iUW YRQDO YDODPHO pOpUH LV LOOHV]NHGHWW YDJ / YDODPHO PiVLN FV~FVSRQWMD LOOHV]NHGHWW /UH  DNNRU D] // ]iUW YRQDODNDWOHKHWHJHWOHQ]iUWYRQDOQDNWHNLQWHQL^+DD]/LOO/pOHLQHN QHP YROQD N|]|V FV~FVSRQWMD DNNRU /W

FVHUpOMN NL RO PyGRQ  KRJ HO{V]|U YH]HVVQN XE{O XWDW / YDODPHO FV~FVSRQWMiED RODQ XWDW DPHOQHN QLQFV N|]|V pOH /HO V H]W D] XWDW HJpV]tWVN NL D] /  ]iUW YRQDOOiD]HO{EELPyGRQ`+DQHPPDUDGWNLpONpV]YDJXQNKDLJHQDNNRU PHJLVPpWHOMND]HO{EELHOMiUiVWpVPLYHODJUiIXQNYpJHVHO{EEYDJXWyEE D]HOMiUiVXQNYpJHWpUpVPHJDGMDD*JUiIHJ]iUW(XOHUYRQDOiW (  7pWHO Ha a G egyszerû összefüggô gráfnak, 2k darab páratlan IRN~FV~FVSRQWMDYDQDNNRUpOHLOHIHGKHW{NNGDUDEQ OW(XOHUYRQDOODO  %L]RQ WiV(JpV]tWVNNLD*JUiIRWNGDUDEpOOHO YpROPyGRQ KRJ *  PLQGHQ FV~FViQDN D IRND SiURV OHJHQ H] QLOYiQ PHJWHKHW{ KD JHOQN DUUD KRJ D] ~M pOHNNHO PLQGLJ SiUDWODQ IRN~ FV~FVRNDW N|VVQN |VV]H* UHHNNRUWHOMHVHGQLIRJD](WpWHOIHOWpWHOHVH]pUWOHV] HJ ]iUW(XOHUYRQDODLVPHOWULYLiOLVDQWDUWDOPD]]DD]~MNGDUDEpOWLV +D D N GDUDE ~M pOW W|U|OMN N GDUDE Q OW

(XOHUYRQDODW NDSXQN 0LpUW QHPNDSKDWXQNNHYHVHEEHWNQiO" VDEL]RQ WiVH]]HONpV] 6LU 9LOOLDP 5RYDQ +DPLOWRQ   EHQ HJ RODQ MiWpNRW KR]RWWIRUJDORPEDPHOQHNDOpQHJHD]YROWKRJHJHO{UHPHJDGRWWJUiI FV~FVSRQWMDLW NHOOHWW EHMiUQL RO PyGRQ KRJ EiUPHO FV~FVEDQ SRQWRVDQ HJV]HUNHOOHWWMiUQLÈOOtWyODJDMiWpNQDNQHPYROWiWW{VLNHUH+DPLOWRQ NRUWiUVDLN|]|WW HILQtFLy $ G = ( E , ϕ ,V )  JUiI + ~WMiW ϕ (e1 ) = (v0 , v1 ), ϕ (e2 ) = (v1 , v2 ),., ϕ (en ) = (vn − 1 , vn ) W +DPLOWRQ~WQDN PRQGMXN KD v0 , v1 ,, vn FV~FVRN PLQG NO|QE|]{N pV H FV~FVSRQWRNRQ NtYO PiV FV~FVSRQWMD QLQFV * QHN HILQtFLy $ G = ( E , ϕ ,V )  JUiI . N|UpW +DPLOWRQN|UQHN PRQGMXN KD WDUWDOPD]]D*PLQGHQFV~FVSRQWMiWLV /iWV]yODJ QDJRQ KDVRQOy SUREOpPD KRJ YDODPHO JUiIQDN D] pOHLW MiUMXN EH SRQWRVDQ HJV]HU YDJ D FV~FVSRQWMDLW $] XWyEEL D]RQEDQ MyYDO QHKH]HEE 6 D] iOWDOiQRV HVHWEHQ

+DPLOWRQXWDN LOOHWYH +DPLOWRQN|U|N NHUHVpVpUHPDVHPLVPHUWLJD]iQMyDOJRULWPXV2SHUiFLyNXWDWiVWHUOHWpKH] WDUWR]LN D] XWD]y JQ|N SUREOpPiMD $] XWD]y JQ|N SUREOpPiMD D]W MHOHQWL KRJ D NHUHVNHGHOPL XWD]yQDN DGRWW YiURVRNDW NHOO EHMiUQLD RO PyGRQ KRJ PLQGHQ YiURVED FVDN HJV]HU PHJ HO pV YpJO YLVV]DWpU D FpJpQHN D V]pNKHOpUH (] HVHWEHQ D JUiI FV~FVSRQWMDL D] XWD]y iOWDO PHJOiWRJDWDQGy YiURVRN D] pOHN SHGLJ D YiURVRNDW |VV]HN|W{ ~WYRQDODN 7HUPpV]HWHVHQ HJHJ ~WQDN MyO PHJKDWiUR]RWW XWLN|OWVpJH LV YDQ V W|EE út esetén célszerû azt az utat választani, melynek a N|OWVpJH PLQLPiOLV +D YDODPHO * JUiI pOHLKH] YDOyV V]iPRNDW UHQGHOQN DNNRU KiOy]DWRNUyO IRODPRNUyO EHV]pOQN 6 QDJRQ WHUPpV]HWHVHQ YHW{GLN IHO PLQLPiOLV költségûLOO maximális nyereségû utak   HVHWOHJ N|U|N NHUHVpVH $] HO{EE HPOtWHWW IHODGDWRN D NRPELQDWRULNXV RSWLPDOL]iOiV WiUJN|UpEH WDUWR]QDN

$N|YHWNH]{ WpWHO PHJIRJDOPD]iVD HO{WW HPOtWMN PHJ KRJ HJ N|U LOO ~W KRVV]iQDEHQQNV]HUHSO{pOHNV]iPiWpUWMN + 7pWHO Ha a G egyszerû gráfban bármely csúcspont foka legalább k k ≥ 2 DNNRUYDQDJUiIEDQHJOHJDOiEENKRVV]~ViJ~N|U  %L]RQ WiV /HJHQ D * JUiIQDN D] / ~W DOHJKRVV]DEE~WMD6H]HQ~WFV~FVSRQWMDLWD NH]G{ SRQWWyO LQGXOYD MHO|OMH UHQGUH v0 , v1 ,., vk , vk +1 ,, vn $]KRJYIRND OHJDOiEE N D]W MHOHQWL KRJ D YW YHO |VV]HN|W{ H pOHQ NtYO PpJ OHJDOiEE N pO LQGXO NL Y EyO (]HQ pOHN PiVLN YpJSRQWMDL szükségszerûen szerepelnek L csúcspontjai N|]|WWPHUWHOOHQNH]{HVHWEHQ|VV]HWN|]pVEH NHUOQpQN D]]DO KRJ D] / ~W D OHJKRVV]DEE /HJHQ H  PiVLN YpJSRQWMD PRQGMXN Y H  YpJSRQWMD Y pV YpJO HN YpJSRQWMD YN (NNRU D] / ~WQDN D YWyO YNLJ WDUWy UpV] ~WMiQDN NpW YpJSRQWMiWN|WL|VV]HHN H]pUWHJN|UWNDSXQNPHOEHQOHJDOiEENpO

YDQVH]]HODEL]RQ WiVNpV] Y H Y H Y H H H H Y YN HN + 7pWHO +D D G = ( E , ϕ ,V ) egyszerû gráf bármely v csúcsának fokára WHOMHVOKRJ δ (v ) ≥ V 2 = n DNNRU*|VV]HIJJ{ 2 %L]RQ WiV /HJHQ X pV Y NpW NO|QE|]{ FV~FVD *QHN $ IHOWpWHO V]HULQW XYDO pV YYHO LV OHJDOiEE Q Q SRQW YDQ |VV]HN|WYH D] XEyO LOOHWYH YE{O LQGXOy pOHN iOWDO D IRNV]iP IHOWpWHO PLDWW $] HO{EE HPOtWHWW XYDO LOOHWYH YYHO N|]YHWOHQO |VV]HN|W|WW SRQWRN N|]|WW YDQ RODQPHOXYDOLVYYHOLV|VV]HYDQN|WYH KDQHPOHQQHLOHQDNNRU* FV~FVDLQDN D V]iPD QDJREE HJHQO{ YROQD PLQW >QQ@  D]D] X pV Y N|]|WWYH]HW~W +D DGRWW D G = ( E , ϕ ,V )  JUiI D FV~FVDLQDN D V]iPiW V = n  V]RNiV * UHQGMpQHNPRQGDQLVpOHLQHNV]iPiW E = q D*JUiIPpUHWpQHNPRQGDQL+DD] XW D] H pO |VV]HN|WL D Y FV~FVVDO DNNRU XW LOO YW D] H pO YpJ SRQWMDLQDN QHYH]]N pV XW LOO YW

V]RPV]pGRVQDN PRQGMXN $] X FV~FVSRQWWDOV]RPV]pGRVFV~FVRNKDOPD]iW1 X YDOMHO|OMN + 7pWHO 22UH  +DD*JUiIUDWHOMHVOKRJUHQGMHQ≥pV EiUPHO NpW QHP V]RPV]pGRV XY FV~FVSRQW IRNiQDN D] |VV]HJH QDJREE HJHQO{*UHQGMpQpO δ (X) + δ (Y) ≥ Q DNNRUQHNYDQ+DPLOWRQN|UH %L]RQ WiV ,QGLUHNW EL]RQ WXQN $]RQ JUiIRN N|]O PHOHNUH D WpWHO IHOWpWHOHL WHOMHVHGQHN GH D] iOOtWiV QHP WHNLQWVN YDODPHOLNHW D]RQ *  JUiIRN N|]O PHOQHN D] pOHLQHN D V]iPD PD[LPiOLV 0D[LPiOLV DEEDQD]pUWHOHPEHQKRJKD* KH]KR]]iYHVV]QNHJRODQHpOWPHOD QHP V]RPV]pGRV X pV Y pOHNHW N|WL |VV]H DNNRU D] tJ NDSRWW * JUiI PiU WDUWDOPD]QL IRJ +DPLOWRQN|UW *  PLQGHQ +DPLOWRQ N|UH WDUWDOPD]]D D] H pOW H]pUW YDQ RODQ / +DPLOWRQ~WMD * QHN PHO XW pV YW N|WL |VV]H OHJHQ H] D] ~W  PHJDGYD ϕ (e1 ) = (v0 , v1 ), ϕ (e2 ) = (v1 , v2 ),., ϕ (en ) = (vn − 1 , vn )  u = v0 , v = vn iOWDO$ v 0 ,

v1 , . , v k , v k + 1 , , v n FV~FVSRQWRNNDONDSFVRODWEDQYHJNpV]UH KRJ KD YNV]RPV]pGRVXYDOD]D]YNHOHPH1 X QDNDNNRUYNQHPHOHPH1 Y QHN (OOHQNH]{HVHWEHQDv0 , vk +1 , vk + 2 ,., vn , vk , vk −1 ,, v0 +DPLOWRQN|UHYROQD* QHN7HKiW D 9^Y` SRQWRN N|]O D] XYDO V]RPV]pGRV SRQWRN QHP  V]RPV]pGRVDN YYHO  H]pUW δ (u) ≤ (n − 1) − δ (v )  V H] XWyEEL HJHQO{WOHQVpJ HOOHQWPRQG D WpWHO IHOWpWHOHLQHN .|YHWNH]PpQ *$ LUDF   Ha az n=2k csúcspontú egyszerû G JUiIEiUPHOSRQWMiQDNDIRNDOHJDOiEENDNNRUYDQ*QHN+DPLOWRQN|UH Az idõrendben való jobb tájékozódás végett egységes jelölés mellett IHOVRUROMXND+DPLOWRQN|U|NUHYRQDWNR]ypUGHNHVHEEHUHGPpQHNHW-HO|OMH D* (ϕ9 JUiIFV~FVSRQWMDLQDNIRNV]iPDLWUHQGUH d1 ≤ d 2 ≤. ≤ d n  |9| Q +DD * (ϕ,V) egyszerû gráfra (2<n) a következô feltételek valamelyike WHOMHVHGLNDNNRUYDQ*QHN+DPLOWRQN|UH *$LUDF  1 ≤ k ≤ n

⇒ d k ≥ 21 n. 22UH   u, v ∈V , de (u, v ) ∉ E ⇒ δ (u) + δ (v ) ≥ n  3yVD/DMRV  1 ≤ k ≤ 1 n ⇒ dk > k . 2 -$%RQG  MN d j , d k ≤ k − 1 ⇒ d j + d k ≥ n. 9&KYiWDO   d k ≤ k  21 n ⇒ d n − k ≥ n − k  9DOyEDQ *EHQ OpWH]LN +DPLOWRQN|U PLYHO D N|YHWNH]PpQ IHOWpWHOHL OpQHJpEHQV]LJRU~EEDNPLQWD + WpWHOIHOWpWHOHL HILQLFLy$*JUiI UpV]JUiIMiWNDGIRN~IDNWRUiQDNPRQGMXNKD L * FV~FVDLQDNKDOPD]DPHJHJH]LNFV~FVDLQDNKDOPD]iYDO LL * EiUPHOFV~FVDD]RQRVIRNV]iP~ $ GHILQtFLyEyO OiWKDWy KRJ YDODPHO * JUiIQDN D . +DPLOWRQN|UH  $ PHOOpNHOW HJEHQ PiVRGIRN~ IDNWRUD *QHN iEUiQOiWKDWyJUiIQDNYDVWDJV]DJJDWRWWLOOHWYHYpNRQYRQDOODOMHO|OWN HJHJ HOV{IRN~ IDNWRUiW (OOHQ{UL]]H OH D .HGYHV 2OYDVy KRJ D KiURP HOV{IRN~ IDNWRU N|]O EiUPHO NHWW{ V]RU]DWD D] iEUiQ OiWKDWy JUiIQDN HJHJ PiVRGIRN~ IDNWRUiW DGMD GH D JUiIQDN QLQFV

+DPLOWRQN|UH GH  D keletkezõ körök természetesen lefedik G csúcsait. 7pWHO Ha a G egyszerû összefüggõ gráfnak van olyan k csúcsa, melyek W|UOpVHXWiQNNRPSRQHQVpUHHVLNV]pWDNNRU*QHNQLQFV+DPLOWRQN|UH %L]RQLWiV Indirekt bizonyitunk. Elegendõ arra gondolni, hogy egy N|UNGDUDESRQWMiQDNW|UOpVHXWiQOHJIHOMHEENUpV]UHHVKHWV]pW 7pWHO Ha a G egyszerû osszefüggõ gráfnak van olyan k pontja melyek W|UOpVH XWiQ N NRPSRQHQVUH HVLN V]pW DNNRU *QHN QLQFV +DPLOWRQ~WMD VSHUV]HPpJNHYpVEpYDQ+DPLOWRQN|UH   %L]RQLWiV,QGLUHNWEL]RQLWXQNWHJNIHOKRJ*QHND]/KDPLOWRQ ~WMDD]D] /UH LOOHV]NHGLN * PLQGHQ FV~FV SRQWMD %iUPHO ~W LJ SHUV]H / LV N GDUDE SRQWMiQDN D W|UOpVpYHO OHJIHOMHEE N UpV]UH ERPOLN V H] HOOHQWPRQG  D WpWHO IHOWHYpVpQHN  PHO V]HULQW OHJDOiEE  N UpV]UH NHOOHQHERPROQLD HILQLFLy /HJHQ D * JUiIQDN G1 , G2 ,., Gk  UHQGUH m1 , m2 ,, mk DG IRN~ IDNWRUDLKD L

KDEiUPHOLMHVHWpQ*LQHNLOOMQHNQLQFVN|]|VpOH LL  D G1 , G2 ,., Gk  UpV]JUiIRN HJWWYpYH WDUWDOPD]]iN * |VV]HV pOpW DNNRU*H]HQNV]iP~IDNWRUV]RU]DWiQDNPRQGMXN *DNRUROMKiWpVW|UHNHGMPLQWDUpJLHN KRJD]~MDWPHJUDJDGKDVGOHJI{EEV]DEiORGH] OHJHQ.XQJ)XFH/XQM,,N|QY IHMH]HW )HODGDWRN  ,JD]ROMD KRJ KD HJ pOW LV WDUWDOPD]y * JUiI PLQGHQ SRQWMiQDN IRNDSiURVDNNRUNLMHO|OKHW{NDJUiIEDQN|U|N~JKRJDJUiIPLQGHQpOH HN|U|NN|]OSRQWRVDQHJEHQV]HUHSHOMHQ  %L]RQ WVD EH KRJ KD D] H pO D] |VV]HIJJ{ * JUiIQDN KtGMD DNNRU * QHP WDUWDOPD] RODQ N|UW PHOEHQ D] H pO V]HUHSHO  HILQtFLy V]HULQWD*|VV]HIJJ{JUiIQDND]HpOpWKtGQDNPRQGMXNKDHW|UOpVpYHOD *E{ONDSRWWJUiIPiUQHP|VV]HIJJ{ %L]RQ WVDEHKRJKDD * |VV]HIJJ{ JUiIQDN QLQFV RODQ N|UH DPHOD]HpOWWDUWDOPD]]DDNNRUHKtGMD*QHN  ,JD]ROMD KRJ KD D * LUiQ WRWW JUiI QHP UHV pV EiUPHO Y

SRQWMiUD δ be (v ) = δ ki (v ) DNNRU*OHIHGKHW{N|U|NNHOROPyGRQKRJEiUPHOpO SRQWRVDQHJN|UEHQV]HUHSHO  %L]RQ WVD EH KRJ D WHOMHV JUiI WHWV]{OHJHV LUiQ WiVD PHOOHWW OpWH]LN RODQ Y SRQWMD PHOE{O EiUPHO PiVLN SRQWKR] YH]HW OHJIHOMHEE NHWW{KRVV]~ViJ~~W  0XWDVVD PHJ KRJ EiUPHO * LUiQ WRWW JUiIEDQ D FV~FVRN NLIRNDLQDNLOOEHIRNDLQDN|VV]HJHD]pOHNV]iPiYDOHJH]LNPHJ 7; Bizonyítsa be, hogy bármely hidat nem tartalmazó összefüggõ G JUiI LUiQ WKDWy RO PyGRQ KRJ HU{VHQ |VV]HIJJ{ OHJHQ  $ * LUiQ WRWW JUiI HU{VHQ |VV]HIJJ{ KD EiUPHO SRQWMiEyO EiUPHO PiVLN SRQWMiEDYH]HWLUiQ WRWW~W 0XWDVVDPHJKRJLJD]DND]DOiEELiOOtWiVRN L +D*QHPUHVJUiI|VV]HIJJ{pVEiUPHOYSRQWMiUD δ be (v ) = δ ki (v ) DNNRU*QHNYDQLUiQ WRWW(XOHUYRQDOD LL +DD*QHPUHVLUiQ WRWWJUiIQDNYDQLUiQ WRWW(XOHUYRQDOD DNNRU*EiUPHOYSRQWMiUD δ be (v ) = δ ki (v ) pV|VV]HIJJ{

0XWDVVDPHJKRJKDD*JUiIQHPUHVpV|VV]HIJJ{DNNRUpOHL EHMiUKDWyN RO PyGRQ KRJ PLQGHQ pOHQ NpWV]HU PHJQN YpJLJ pV YLVV]D WpUQN D NLLQGXOiVL SRQWED $] pOHN EHMiUiVD ~J LV HOYpJH]KHW{ KRJ PLQGHQpOWPLQGNpWLUiQEDQSRQWRVDQHJV]HUMiUXQNEH   /HJHQ D * JUiI RODQ UpV]JUiIMD QHN PHO WDUWDOPD]]D D  Y FV~FVSRQWMiW pV * (XOHUJUiI IHOWHVV]N PpJ KRJ  YE{O WHWV]{OHJHVHQ EHMiUKDWy 7|U|OMN * pOHLW pV D YLVV]DPDUDGW L]ROiOW SRQWMDLW QHN D PHJPDUDGW JUiIRW MHO|OMH * 0XWDVVD PHJ KRJ  pV  LV YE{O WHWV]{OHJHVHQ EHMiUKDWy  $ * JUiIRW YE{O WHWV]{OHJHVHQ EHMiUKDWyQDN PRQGMXNKDYE{OLQGXOYDpVPLQGLJEHQHPMiUWpOHQKDODGYDV]NVpJNpSSHQ *QHNYDODPHO(XOHUYRQDOiWNDSMXN 0XWDVVDPHJKRJKDSiURVV]iP~XWDW~JNDSFVROXQN|VV]HKRJ NH]G{SRQWMXNXUDYpJSRQWMXNYUHLOOHV]NHGLNpVXLOOYNtYOPiVN|]|V SRQWMXN QLQFV DNNRU PLQG XEyO PLQG YE{O WHWV]{OHJHVHQ

EHMiUKDWy JUiIRW NDSXQN0XWDVVDPHJKRJEiUPHOXEyOLOOYE{OWHWV]{OHJHVHQEHMiUKDWy *JUiIHO{iOOtWKDWyD]HO{EELPyGRQ  ,JD]ROMD KRJ D NHWW{QpO W|EE SRQWMXNEyO WHWV]{OHJHVHQ EHMiUKDWy*JUiIRNN|U|N  -HO|OMH D * LUiQ WRWW JUiI FV~FVDLW UHQGUH v 0 , v1 , . , v k , v k + 1 , , v n  i =n PXWDVVDPHJKRJD ∑ δ ki (vi ) − δ be (vi ) V]iPSiURV i=0  9L]VJiOMD PHJ KRJ D [HV VDNNWiEOiW EH OHKHW H MiUQL HJHWOHQ OyYDO OyXJUiVRNNDO RO PyGRQ KRJ PLQGLJ RODQ PH]{UH OpSQN PHOHQ NRUiEEDQ PpJ QHP MiUWXQN  7HWV]{OHJHVHQ YiODV]WRWW PH]{U{O LQGXOKDWXQN  9pJLJ OHKHW H MiUQL D] [|V VDNNWiEOiW D] HO{EE HPOtWHWW PyGRQ"  %L]RQ WVXN EH KRJ KD HJ WiUVDViJQDN EiUPHO WDJMD LVPHU D WiUVDViJEyO OHJDOiEE N HPEHUW DNNRU N|]ON OHOWHWKHW{ HJ NHUHN DV]WDO PHOOp OHJDOiEE N V]HPpO RO PyGRQ KRJ PLQGHQNLQHN D NpW V]RPV]pGMD LVPHU{VH LV HJEHQ  )HOWpWHOH]]N KRJ N≥

pV D] LVPHUHWVpJHN N|OFV|Q|VHN  %L]RQ WVD EH KRJ KD D] HO{EEL IHODGDWEDQ HPOtWHWW WiUVDViJ  I{E{O iOO pV N  DNNRU PLQG D KDWDQ OHOWHWKHW{N HJ DV]WDO PHOOp D] HO{]{IHODGDWIHOWpWHOHLQHNPHJIHOHO{HQ  /HJHQ D * JUiI FV~FVSRQWMDLQDN D V]iPD Q≥ 0XWDVVD PHJ KRJ ha az n pontú egyszerû gráfban bármely ((n-1)/2)>k pozitív egész k-ra a kQiO QHP QDJREE IRN~ SRQWRN V]iPD NHYHVHEE PLQW N DNNRU D * JUiI |VV]HIJJ{ 19; Mutassa meg ha a egyszerû összefüggõ G gráf K körének bármely e pOpQHNW|UOpVHXWiQD*OHJKRVV]DEE~WMiWNDSMXNDNNRU.+DPLOWRQN|UH* QHN 20; Igazolja, hogy ha egy n csúcspontú egyszerû gráf bármely OHJKRVV]DEE~WMiQDNYpJSRQWMDLIRNV]iPDLQDN|VV]HJHQDNNRUDOHJKRVV]DEE XWDNN|]|WWYDQRODQPHOQHNDYpJSRQWMDLV]RPV]pGRVDN  0XWDVVD PHJ KRJ KD YDODPHO VDNN YHUVHQHQ PLQGHQNL PLQGHQNLYHO HJV]HU PpUN{]|WW pV G|QWHWOHQ QHP YROW DNNRU D YHUVHQ]{N VRUED UHQGH]KHW{N

RO PyGRQ KRJ PLQGHQNL J{]|WW D] XWiQD N|YHWNH]{ HOOHQ  %L]RQ WVD EH KRJ D OHJDOiEE  SRQW~ WHOMHV JUiIQDN EiUPHO LUiQ WiVDPHOOHWYDQLUiQ WRWW+DPLOWRQ~WMD ,UiQ WVDD]V]|JSRQW~WHOMHVJUiIRWROPyGRQKRJQHOHJHQ DNDSRWWJUiIQDNLUiQ WRWW+DPLOWRQN|UH 24. Rajzoljon olyan 6 pontú 11 élû egyszerû gráfot melynek nincs +DPLOWRQN|UH   +HOH]]HQ HO D] RNWDpGHU PLQGHQ ODSMiUD HJHJ D ODSRW SRQWRVDQ IHG{ WHWUDpGHUW 0XWDVVD PHJ KRJ D] tJ OpWUH M|WW WHVW pOKiOy]DWiEyOiOOyJUiIQDNQLQFVHQVHP+DPLOWRQN|UHVHP+DPLOWRQ~WMD  +iQ +DPLOWRQN|UH YDQ D WHWUDpGHU LOO KH[DpGHU NRFND JUiIMiQDN 27; Ha egy összefüggô gráf nem egyrétûen járható be (tehát legalább QpJ SiUDWODQ IRN~ FV~FVRW WDUWDOPD]  DNNRU OHJDOiEE NpW NO|QE|]{ PLQLPiOLV OHIHGpVH YDQ  $ OHKHW{ OHJNHYHVHEE YRQDOEyO iOOy OHIHGpVHLW HJ JUiIQDN PLQLPiOLV OHIHGpVQHN PRQGMXNpV HJ YRQDO KDOPD] OHIHG{ KD D

JUiIPLQGHQpOpWOHJDOiEEHJV]HUWDUWDOPD]]D  6]HSDUiOyKDOPD]RNV]pWYiJyKDOPD]RNYiJiVRNSiURV JUiIRN $ OpSFV{NHW V]HPE{O PiVV]XN PHJ PLYHO KiWUiOYD YDJ ROGDOD]YD LJHQ NpQHOPHWOHQ YROQD -XOLR &RUWi]DU $] |VV]HIJJ{ SDUNRN 8WDVtWiVRN D OpSFV{ PHJPiV]iViKR]  .ULWHULRQ  R *DNUDQ YDQ DUUD V]NVpJQN KRJ YDODPHO  JUiI RODQ UpV]JUiIMiUyO EHV]pOMQN PHOHW G = ( E , ϕ ,V )  E{O YDODPHO pOHLQHN HOKDJiViYDONDSWXQN+DDW|U|OWpOHNKDOPD]iW)MHO|OLDNNRU DYLVV]DPDUDGWUpV]JUiIRWU|YLGHQG = ( E − F , ϕ ,V ) HOMHO|OMN HILQtFLy $ G = ( E , ϕ ,V ) egyszerû összefüggô gráf éleinek F UpV]KDOPD]iW V]HSDUiOy KDOPD]QDN PRQGMXN KD D G = ( E − F , ϕ ,V )  JUiI QHP|VV]HIJJ{ 1HP UHV V]HSDUiOy KDOPD] PLQGLJ OpWH]LN KD OHJDOiEE NpW FV~FVDYROWD]|VV]HIJJ{*JUiIQDNPLYHOEiUPHOJUiIHVHWpQ * |VV]HV pOHLQHN D KDOPD]D WULYLiOLVDQ V]HSDUiOy KDOPD] $ G = ( E , ϕ ,V )

JUiIFV~FVDL9KDOPD]iQDNQHPUHVUpV]KDOPD]DL:pV: OHJHQHNDGRWWDN:pV: UpV]KDOPD]RNUDWHOMHVHGMHQPpJKRJ : 9: $]D]:: GLV]MXQNWDNpVXQLyMXN9 HILQtFLy $ G = ( E , ϕ ,V ) egyszerû összefüggô gráf éleinek F UpV]KDOPD]iW:: UHYRQDWNR]yODJV]pWYiJyKDOPD]QDNPRQGMXNKD )HOHPHL:SRQWMDLWN|W|WWpN|VV]H: SRQWMDLYDO 7pWHO $ G = ( E , ϕ ,V ) egyszerû gráf, akkor és csak akkor |VV]HIJJ{KD9WQHPOHKHWIHOERQWDQL:: QHPUHVGLV]MXQNW UpV]KDOPD]RN XQLyMiUD RO PyGRQ KRJ        ha ∀e ∈ E é s ϕ (e) = (v1 , v2 ) ⇒  (v1 , v2 ∈W ) vagy (v1 , v2 ∈W )    %L]RQ WiV$WpWHOXWROVyVRUiQDNDIRUPXOiMiEDQV]HUHSO{ YDJ ~Q NL]iUy YDJ $ WpWHO XWROVy VRUD YpJO LV D]W PRQGMD KRJ QLQFV RODQ pO PHO : YDODPHO SRQWMiW N|WQp |VV]H : SRQWMiYDO 0iV V]yYDO KD OpWH]QHN D WpWHOEHQ HPOtWHWW WXODMGRQViJRNNDO UHQGHONH]{ : :  KDOPD]RN DNNRU * QHP

|VV]HIJJ{ +D XJDQLV * |VV]HIJJ{ YROQD DNNRU OpWH]QH :E{O LQGXOy: EHQYpJ]{G{~W6D]~WQDNOHJDOiEEHJRODQHpOH DPHOQHNHJLNYpJSRQWMD:EHPiVLN: EHHVQH )RUGtWYD KD * QHP |VV]HIJJ{ DNNRU OHJDOiEE NpW NRPSRQHQVHYDQ/HJHQD]HJLN G1 = ( E1 , ϕ1 ,V1 ) KD: 9QHNpV: 9 9 QHNYiODV]WMXNDNNRUOiWKDWyDNRPSRQHQVGHILQtFLyMDPLDWW QLQFVRODQHpOPHO:WN|WQp|VV]H: YHO  HILQtFLy$*JUiI)V]HSDUiOyKDOPD]iWYiJiVQDNQHYH]]N KD ) QHN QLQFV RODQ YDOyGL )  UpV]KDOPD]D DPHO V]LQWpQ * V]HSDUiOyKDOPD]DYROQD 1LOYiQ D]W LV PRQGKDWQiQN KRJ D YiJiV PLQLPiOLV V]HSDUiOiV +D YDODPHO ) V]HSDUiOy KDOPD] D * JUiIRW  YDJ W|EE NRPSRQHQVUH ERQWRWWD IHO DNNRU ) QHP OHKHW YiJiV PHUW EiUPHO H )EpOL pOUH )^H` V]HSDUiOy KDOPD] 8JDQLV D] H OHJIHOMHEENpWNRPSRQHQVWN|W|VV]H 9HJNpV]UHD]WLVKRJHJYiJiVV]NVpJNpSSHQV]pWYiJy KDOPD] LV GH IRUGtWYD QHP LJD] 9DQ RODQ * JUiI

pV RODQ ) V]pWYiJyKDOPD]D*QHNPHOQHPYiJiV0XWDVVRQOHJDOiEEHJHW $IHQWLHNV]HULQWLJD]D]DOiEELiOOtWiV 7pWHO $ * |VV]HIJJ{ JUiI EiUPHO IHV]tW{ IiMiQDN YDQ OHJDOiEEHJN|]|VpOH*EiUPHOV]pWYiJyKDOPD]iYDO 0HJMHJ]pV 9HJN pV]UH D * JUiI 7 IHV]tW{ IiMD RODQ PLQLPiOLVDQ |VV]HIJJ{ UpV]JUiIMD *QHN PHO  FV~FVDLW |VV]HN|WL$*JUiIQDN)V]pWYiJyKDOPD]DSHGLJRODQPLQLPiOLV KDOPD]DpOHNQHNPHO*EL]RQRVFV~FVDLWHOYiODV]WMDHJPiVWyO Emlékezzünk arra is , hogy a G egyszerû összefüggô gráf T IHV]tW{IiMDRODQPD[LPiOLVDQ|VV]HIJJ{UpV]JUiIMD*QHNPHO QHPWDUWDOPD]N|UW 7pWHO &DOH  $] Q V]|JSRQW~ .Q WHOMHV JUiI NO|QE|]{ IHV]tW{IiLQDNDV]iPDQQ $ WpWHO N|]LVPHUW EL]RQ WiVDL NLVVp NRPSOLNiOWDEEDN D] iWODJQiOD]pUWD]WLWWPHOO{]]N .UXVNDODOJRULWPXV Legyen adott egy G egyszerû összefüggô JUiI pV OHJHQHN D] pOHL V~OR]RWWDN $ G = ( E , ϕ ,V )   JUiI pOHL V~OR]RWWDN KD * EiUPHO H

pOpKH] KR]]i YDQ UHQGHOYH HJ Z YDOyVV]iP6RNIHODGDWQiODV~ONpQWV]HUHSO{YDOyVV]iPRNQHP QHJDWtYDN $ .UXVNDODOJRULWPXV YpJO LV DUUD YDOy KRJ PHJKDWiUR]]D HJ V~OR]RWW JUiI PLQLPiOLV IHV]tW{ IiMiW * YDODPHO IHV]tW{ IiMiW PLQLPiOLVQDN PRQGMXN KD D] ) pOHLKH] UHQGHOWV~ORN|VV]HJHPLQLPiOLVD]D]*EiUPHOPiV) IHV]tW{ IiMD HVHWpQ D] )  pOHLKH] WDUWR]y V~ORN |VV]HJH QDJREE YDJ HJHQO{ PLQW D] ) pOHLKH] WDUWR]y V~ORN |VV]HJH )RUPXOiYDO OHtUYD D] HO{EELW ∑ w(ei ) ≤ ∑ w(ei )  WHOMHVO * EiUPHO )  IHV]tW{ ∀ei ∈E ( F ) ∀ei ∈E ( F ) IiMiUD DKRO ( )  LOO ( )  MHO|OL ) LOO )  pOHLQHN D KDOPD]iW $ .UXVNDO DOJRULWPXV OpQHJH U|YLGHQ D N|YHWNH]{ 9iODVV]XN HO{V]|U * pOHL N|]O  ( E{O  D PLQLPiOLV V~O~W HW $ PiVRGLN OpSpVEHQ ( ( * ^H`E{O YiODVV]XN D HW JHOYH DUUD KRJ D] H H pOHN QH DONRVVDQDN *EHQ N|UW 6  iOWDOiEDQ D] DOJRULWPXV NLN OpSpVH

DEEyO iOO KRJ D] E k = E (G ) − {e1 , e2 ,., ek −1}  pO KDOPD]EyO YiODVV]XQN HJ RODQ PLQLPiOLV V~O~HNWPHODPiUNLYiODV]WRWW e1 , e2 ,., ek −1 pOHNNHOHJWWQHP DONRW N|UW *EHQ +D D PRQGRWW WXODMGRQViJJDO UHQGHONH]{ H pO QHP OpWH]LN DNNRU D] DOJRULWPXV YpJHW pUW $ NRQVWUXNFLyEyO QLOYiQYDOy KRJ D] HUHGPpQO NDSRWW ) ID JUiI IHV]tW{ IiMD *QHN ) PLQLPDOLWiViW LQGLUHNW ~WRQ PXWDVVXN PHJ 7HJN IHO KRJD]) IHV]tW{IDpOHLKH]UHQGHOWV~ORN|VV]HJHNLVHEEPLQW D])KH]UHQGHOWHN|VV]HJHpV)QHNpV) QHND]pOHLLVV~OXN QDJViJDL V]HULQW VRUED UHQGH]HWWHN D]D] w(e1 ) ≤ w(e2 ) ≤. ≤ w(en −1 )  LOO w(e1 ) ≤ w(e2 ) ≤. ≤ w(en − 1 )  (] D]W MHOHQWL KRJ OHJDOiEE HJ pON NO|QE|]LN /HJHQ D] D VRUUHQGEHQ D] HOV{ SO HM H] D]W MHOHQWHQp KRJ QHP D PLQLPiOLV V~O~ pOW YiODV]WRWWXN D MLN OpSpVEHQVH]HOOHQWPRQGiV 7pWHO (J * |VV]HIJJ{ JUiIEDQ EiUPHO ) V]pWYiJy KDOPD]

EiUPHO3]iUWYRQDOQDNSiURVVRNpOpWWDUWDOPD]]D %L]RQ WiV /HJHQ DGRWW D * JUiI FV~FVDLQDN KDOPD]D NpW QHPUHV:: GLV]MXQNWUpV]KDOPD]DLQDNXQLyMD6D])V]pWYiJy KDOPD]D *QHN :: UH YRQDWNR]yODJ pV OHJHQ DGRWW HJ 3 ]iUW pOVRUR]DWD *QHN ,QGXOMXQN HO YDODPHO 3EHOL FV~FVSRQWEyO PHO HJEHQ :QHN LV HOHPH +D 3 YDODPHO H pOH iWPHJ : EH DNNRU D ]iUWViJ PLDWW RODQ H pO LV OHV] DPHOLNNHO YLVV]DMXWXQN:EH+DDWRYiEELEDUDQJROiVXQNVRUiQ~MyODJ: EH EyNOiV]QiQN H pOHQ D ]iUWViJ PLDWW LVPpW :EH NHOO WpUQQN YDODPHOH pOOHOpVtJWRYiEEDPtJYpJLJQHPSRURV]NiOXQND 3 ]iUW YRQDO YDODPHQQL pOpQ $] ) KDOPD] V]pWYiJy YROWD PLDWW D]HH HH HNHN pOHNHOHPHL)QHNLJD]WHKiWDWpWHO 1pKiQ ROGDOODO HO{EE PiU EHV]pOWQN HJHJ pUGHNHVHEE JUiIUyOPLQWSpOGiXOD]QFV~FVSRQW~WHOMHVJUiIUyO$V]pWYiJy KDOPD]NDSFViQPHJHPOtWMNDNSDUWLFLRQiOKDWyJUiIRNDW HILQtFLy $ G = ( E , ϕ ,V ) 

JUiIRW N SDUWLFLRQiOKDWyQDN PRQGMXN KD PHJDGKDWy 9QHN RODQ 9 = 9 ∪ 9 ∪∪9 N  RV]WiOR]iVD DKRO D 99  9 N  KDOPD]RN HJLNH VHP UHV pV QLQFV RODQ pO PHOQHN PLQGNpWYpJSRQWMDXJDQD]RQ9LKDOPD]EDQYROQD 3iURVJUiIRN $JDNRUODWEDQpVD]HOPpOHWEHQLVNLWQWHWHWWV]HUHSHYDQ DN HVHWQHNPiVQpYHQDSiURVJUiIRNQDN HILQtFy $ G = ( E , ϕ ,V ) W SiURV JUiIQDN PRQGMXN KD 9 IHOERPOLN NpW QHP UHV GLV]MXQNW UpV]KDOPD]iUD 9 = 9 ∪ 9  DKRO QLQFVRODQH pO PHOUH D] WHOMHVHGQH KRJ ϕ (e) = (v1 , v2 )  pV v1 , v2 ∈Vi DKROL   3iURV JUiIUD SpOGD OHKHW HJ HVWpW YpJLJ WiQFROy IDUVDQJL WiUVDViJ DKRO D FV~FVRN D] HPEHUHN pV NpW FV~FV |VV]H YDQ N|WYH KD D] DGRWW HPEHUHN D] HVWH VRUiQ WiQFROWDN HJPiVVDO 7HJJN IHO KRJ FVDN SiURV WiQFRNDW WiQFROWDN pV EiUPHOLN IpUIL FVDN Q{YHO pV EiUPHOLN Q{ FVDN IpUILYDO WiQFROW $ WiUVDViJ K|OJ WDJMDLW MHO|OYH D FV~FVRN HJLN

V D WiUVDViJ IpUILWDJMDLWMHO|OYHDFV~FVRNPiVLNKDOPD]iQDNQLOYiQSiURV JUiIRWNDSWXQN 7pWHO +D D * SiURV JUiI DNNRU EiUPHO . N|UpQHN D] pOHLQHNDV]iPDSiURV %L]RQ WiV -iUMXN YpJLJ . pOHLW PRQGMXN  YDODPHO 9E{O YDOy9SRQWMiWyONH]GYH$]HpOYSRQWEDYLV]PHO9HOHPH PLYHO 9EpOL SRQW QLQFV |VV]HN|WYH 9EpOL SRQWWDO YE{O 9 EpOL SRQWED YLV] H PLYHO 9EpOL SRQWRNDW QHP N|W |VV]H pO /iWKDWy KRJ D N|U pOHLW HJPiVXWiQ EHMiUYD YiOWDNR]YD PHJQN 9E{O 9EH LOO 9E{O 9EH .|UU{O OpYpQ V]y KD 9E{O UDMWROWXQN DNNRU RGD LV NHOO YLVV]D IXWQXQN V H]pUW D] pOHN V]iPDYDOyEDQSiURV HILQtFLy $ * SiURV JUiI pOHLQHN 0 UpV]KDOPD]iW SiURVtWiVQDNPRQGMXNKD0EiUPHOpOpQHNQLQFVN|]|VYpJSRQWMD 0iV V]yYDO 0 HOHPHL SiURVtWMiN  HJPiVKR] UHQGHOLN  D * SiURV JUiI FV~FVSRQWMDLW 0W WHOMHVQHN PRQGMXN KD 0 OHIHGL * FV~FVDLW V PD[LPiOLVQDN KD QHP OpWH]LN 0QpO QDJREE

HOHP V]iP~0 SiURVtWiVD*QHN $ * JUiI pOHLQHN 0 KDOPD]iW IJJHWOHQQHN PRQGMXN KD 0 EiUPHO NpW pOpQHN QLQFV N|]|V YpJSRQWMD $] 0 IJJHWOHQ pO KDOPD]W WHOMHVQHN PRQGMXN KD 0 YpJSRQWMDL N|]|WW * PLQGHQ SRQWMDV]HUHSHO$]0HOHPHLNpWD]RQRVV]iPRVViJ~UpV]KDOPD]UD ERQWMiN*SRQWMDLWH]pUWQLOYiQLJD]DN|YHWNH]{iOOtWiV 7pWHO +D D * JUiIEDQ YDQ IJJHWOHQ WHOMHV 0 pO KDOPD] DNNRU*FV~FVDLQDNV]iPDSiURV $] 0 KDOPD]W PD[LPiOLVQDN PRQGMXN KD * pOHLQHN QLQFV RODQ0 UpV]KDOPD]DPHOIJJHWOHQpVW|EEHOHPHYDQPLQW0 QHN -HOH *pIPD[ $  JUiI FV~FVSRQWMDLQDN YDODPHO 6 UpV]KDOPD]iW OHIRJy OHV]~Uy  SRQWKDOPD]QDN PRQGMXN KD * EiUPHO pOpQHN OHJDOiEE D] HJLN YpJSRQWMD 6EHQ YDQ -HOH *OSPLQ 7pWHO .{QLJ pQHV   %iUPHO SiURV JUiI IJJHWOHQ pOHLQHN PD[LPiOLV V]iPD HJHQO{ D] pOHNHW OHIRJy SRQWRN PLQLPiOLVV]iPiYDO  %L]RQ WiV $] KRJ D OHIRJy SRQWRN PLQLPiOLV V]iPD QDJREE

HJHQO{ *pIPD[≤OSPLQ  PLQW D PD[LPiOLVDQ IJJHWOHQ pOHN V]iPDDGHILQtFLyEyON|]YHWOHQODGyGLN/HJHQD*JUiISiURV D]D]DGRWW*FV~FVDLQDNHJV = V1 U V2 SDUWtFLyMD7HJNIHOKRJ 9 pV 9 SRQWRNDW NpW HJPiVVDO SiUKX]DPRV HJHQHVHQ YHWWN IHO  1HYH]]N 9 SRQWMDLW IHOV{ SRQWRNQDN pV 9 SRQWMDLW DOVy SRQWRNQDN .{QLJ pQHV pV (JHUYiU -HQ{ D] DV pYHNEHQ NLIHMOHV]WHWWHN HJ PyGV]HU D PD[LPiOLV IJJHWOHQ pOHN PHJKDWiUR]iViUD PHOHW UyOXN PDJDUPyGV]HUQHN LV V]RNWDN QHYH]QL(PyGV]HUUHOOHKHWD]HOOHQNH]{LUiQ~HJHQO{WOHQVpJHW *pIPD[≥OSPLQ EL]RQ WDQL 0D[LPiOLV V]iP~ pOW WDUWDOPD]y SiURVtWiV NHUHVpVH PDJDU PyGV]HUUHO7HJNIHOKRJDSiURVJUiIXQNFV~FVDL$LOO%QHP UHV GLV]MXQNW KDOPD]RNQDN D] HOHPHL pV $EyO $ED LOO %E{O %EH QHP IXW pO /HJHQ DGRWW *QHN HJ 0 SiURVtWiVD  0 OHKHW UHV LV  *QHN YDODPHO HHHHHN ~WMiW DOWHUQiOy

~WQDNIRJMXNQHYH]QLKDD]pOHNIHOYiOWYDHOHPHL0QHNLOOHWYH $ $  $ $ % % % %  ( * 0 QHN SpOGiXO H∈0 H∉0H∈0 H∉ 0-HO|OMHPRVWD*SiURVJUiIFV~FVSRQWMDLQDNDKDOPD]iW$ ∪% (POpNH]WHW{O PHJMHJH]]N KRJ $ LOO % QHP UHV pV GLV]MXQNW WRYiEEi EiUPHO pO FVDN $EyO YDOy SRQWRW N|WKHW |VV]H  %EHOL SRQWWDO  YDJ PRQGKDWMXN IRUGtWYD LV KRJ FVDN %EHOL SRQW YDQ |VV]HN|WYH $EpOL SRQWWDO  $ V]|YHJEH KHOH]HWWiEUiQYDVWDJYRQDOODOMHO|OWN0pOHLW$%MHO|OL$ LOO % 0 iOWDO OH QHP IHGHWW SRQWMDLW +D WDOiOXQN RODQ DOWHUQiOy HHHHHN XWDW PHO %E{O LQGXO pV $EHQ YpJ]{GLN DNNRU D] HHHHHN út M-ben lévô páros indexû éleit cseréljük ki a nem M-ben lévô páratlan indexûekre. Az így QHUW ~M 0  SiURVtWiVD *QHN pV 0 QHN HJJHO W|EE HOHPH YDQ PLQW0QHN$N|YHWNH]{OpSpVEHQPHJKDWiUR]]XND]0 K|]WDUWR]y $ %  KDOPD]RNDW pV NHUHVVQN

RODQ DOWHUQiOy XWDW PHO %  E{O LQGXO pV $-ben végzôdik. Az alternáló út páros indexû éleit M-bôl törölve, s M-höz csatolva az út páratlan indexû pOHLW D *QHN HJ 0  SiURVtWiViW NDSMXN PHOQHN HJJHO W|EE HOHPH YDQ PLQW 0 QHN $] DOJRULWPXVW QLOYiQ DGGLJ OHKHW IROWDWQLDPtJWDOiOXQNDIHQWHPOtWHWWWtSXV~DOWHUQiOyXWDNDW 0HJOHKHW PXWDWQL KRJ PLNRU PiU QHP OHOQN DONDOPDV DOWHUQiOy  XWDW D] XWROVy OpSpVEHQ NDSRWW 0 SiURVtWiV Q  SiURVtWiV PD[LPiOLV HILQtFLy: Ha a G egyszerû gráf bármely csúcsának a foka k, DNNRU*WNUHJXOiULVQDNPRQGMXN $ .HGYHV 2OYDVy KD NLFVL N pUWpNHNUH OHUDM]ROMD D N V]|JSRQW~ WHOMHV JUiIRW pV]UH IRJMD YHQQL KRJ D]RN N regulárisak. S valószínûleg azt is belátja, hogy ha valamely IiQDN NHWW{QpO W|EE FV~FVD YDQ DNNRU D] QHP OHKHW UHJXOiULV VHPPLOHQNUDVHP HILQtFLy$*JUiIRWNV]RURVDQ|VV]HIJJ{QHNPRQGMXNKD EiUPHO NpW NO|QE|]{ YY  FV~FVD

N GDUDE RODQ ~WWDO N|WKHW{ |VV]HPHOHNQHNDYY NtYOPiVN|]|VFV~FVSRQWMXNQLQFVHQ 1HP QHKp] pV]UHYHQQL KRJ D N V]|JSRQW~ WHOMHV JUiI (k − 1) V]HUHVHQ |VV]HIJJ{ V D]W VHP KRJ KD YDODPHO * JUiI QHP WDUWDOPD]KLGDWDNNRUD]OHJDOiEENpWV]HUHVHQ|VV]HIJJ{ 6]iOOtWiVL SUREOpPiN HOHNWURPRV KiOy]DWRN HOHP]pVpQpO általában gyakran szükségesek a következõ fogalmak illetve WpWHOHN HILQtFLy $ * JUiI XY QHP V]RPV]pGRV FV~FVDLW OHIRJy SRQWKDOPD]*FV~FVDLQDNRODQUpV]KDOPD]DDPHOEiUPHOXWpV v-t összekötõ l útnak tartalmazza legalább egy belsõ u-tól v-tõl különbözõ pontját. Jele: uv-LP 1LOYiQD]RNDOHIRJySRQWKDOPD]RND]pUGHNHVHNPHOHNQHN a lehetõ legkevesebb elemük van. HILQtFLy $ * JUiI SRQWIJJHWOHQ XY~WMDLQDN D KDOPD]iQ olyan u kezdõpontú ill. v végpontú utak halmazát értjük, DPHOHNQHN H NpW FV~FV SRQWRQ NtYO PiV N|]|V SRQWMXN QLQFVHQ -HOHXY3)8

$SRQWIJJHWOHQXWDNQDNDPD[LPiOLVV]iPDD]DPLiOWDOiEDQ pUGHNHV 7pWHO+DD*JUiIEDQXpVYQHPV]RPV]pGRVFV~FVRNDNNRU D SRQWIJJHWOHQ XWDN PD[LPiOLV V]iPD NLVHEE YDJ OHJIHOMHEE egyenlõ az u,v csúcsokat legkevesebb ponttal lefogó ponthalmaz HOHPHLQHNDV]iPD)RUPXOiYDOtUYD PD[ XY − 3)8 ≤ PLQ XY − / 3  $ WpWHO pV D IRJDOPDN MREE PHJpUWpVH YpJHWW DMiQOMXN D Kedves Olvasó figyelmébe a következõ példát. A kékek 2 csapata XEDQ  LOO YEHQ IRJODO KHOHW $ SLURVRN IHODGDWD KRJ PHJDNDGiOR]]iN D NpNHN pULQWNH]pVpW 1LOYiQ PLQGHQ ÄIJJHWOHQ ~WUD NL NHOO NOGHQLN HJHJ HJVpJHW DPHOHN OHIRJMiN D] összes szóba jöhetõ útat.  7pWHO+DD*JUiIEDQXLOOYQHPV]RPV]pGRVDNNRUD]XW v-vel összekötõ pontfüggetlen utak maximális száma megegyezik az XYW OHJNHYHVHEE SRQWWDO OHIRJy SRQWKDOPD] HOHPHLQHN D V]iPiYDO-HOEHQ PD[ XY − 3)8 ≡ PLQ XY − / 3 

(]WDWpWHOWV]RNiVRVSRQW0HQJHUWpWHOQHNPRQGDQLPLYHOD tételt elõször K. Menger publikálta 1927-ben HILQtFLy$]XYXWDNDWOHIRJypOKDOPD]RQD*JUiIpOHLQHN RODQ(¶UpV]KDOPD]iWpUWMNDPHOWDUWDOPD]]DEiUPHOXY~WQDN OHJDOiEEHJpOpW-HOHXY/e HILQtFLy eOIJJHWOHQ XY XWDN KDOPD]iQ D * JUiI RODQ útjait értjük, amelyek közül bármely kettõnek nincs közös éle (közös csúcsuk azonban lehet olyan is, mely az u-tól ill. v-tõl is különbözõ). Jele: uv-ÉFU 7pWHOBármely G gráfban az u-t v-vel összekötõ élfüggetlen utak maximális száma kisebb vagy egyenlõ, mint az uv utakat OHIRJy EiUPHO pOKDOPD] HOHPHLQHN D V]iPD .LFVLW U|YLGHEEHQ MHO|OYH PD[ XY − ()8 ≤ PLQ XY − / (  7pWHO pO0HQJHUWpWHO Bármely G gráfban az uv-t összekötõ élfüggetlen utak maximális száma egyenlõ az uv utakat lefogó PLQLPiOLVDQ OHIRJy pOHNQHN D V]iPiYDO  .pSOHWWHO tUYD PD[ XY − ()8 ≡ PLQ XY − / (  )HODGDWRN  %L]RQ WVD

EH KRJ EiUPHO YW{O ZLJ KDODGy pO VRUR]DW WDUWDOPD]YW{OZLJKDODGyXWDW  %L]RQ WVDEHKRJKDXpVY |VV]HN|WKHW{N YRQDOODO YDODPLQW Y pVZLVDNNRUXpVZLV|VV]HN|WKHW{HJYRQDOODO  %L]RQ WVD EH KRJ PLQGHQ XW pV YW |VV]HN|W{ YRQDO PHO QHP ~W IHOERQWKDWy HJ XW YYHO |VV]HN|W{ ~WUD pV HJ YDJ W|EE N|UUH ,O PyGRQ FVXSiQ D] XWDN PLQLPiOLVDN DEEDQ D] pUWHOHPEHQ KRJ pOHLNQHN HJHWOHQYDOyGLUpV]KDOPD]DVHPN|WL|VV]HYpJSRQWMDLNDW  %L]RQ WVDEHKRJHJ]iUWLUiQ WRWWYRQDO PHO QHP N|U NpW YDJW|EELUiQ WRWWN|UUHERQWKDWy  0XWDVVDPHJKRJXEyOYEHYLY{LUiQ WRWW YRQDO PHO QHP ~W IHOERQWKDWy XEyO YEH YLY{ LUiQ WRWW ~WUD pV HJ YDJ W|EE LUiQ WRWW N|UUH  ,JD]ROMD KRJ KD  WDUWDOPD] YE{O ZEH LOO ZE{O YEH YH]HW{ LUiQ WRWWYRQDODWDNNRUWDUWDOPD]]iUWLUiQ WRWWYRQDODW LUiQ WRWW vonalban az élek nem ismétlõdhetnek). Adjon olyan példát a fenti IHOWpWHOHN PHOOHW PLNRU

LV QHP OpWH]LN RODQ ]iUW LUiQ WRWW YRQDO PHO YUHpVZUHLVLOOHV]NHGLN   ,JD]ROMD KRJ KD D  LUiQ WRWW JUiI PLQGHQ SRQWMiQDN EHIRND SR]LWtY DNNRU  V]NVpJNpSSHQ FLNOLNXV JUiI  $ * JUiI FLNOLNXV KD WDUWDOPD]N|UW  0XWDVVD PHJ KRJ HJ YpJHV LUiQ WRWW  JUiI DNNRU pV FVDN DNNRUHU{VHQ|VV]HIJJ{KDOpWH]LNRODQ]iUWLUiQ WRWWpOVRUR]DWDPHO PLQGHQ pOpW OHJDOiEE HJV]HU WDUWDOPD]]D   HU{VHQ |VV]HIJJ{ KD EiUPHOYFV~FViEyOYH]HWLUiQ WRWW~WEiUPHOPiVLNZFV~FViED  %L]RQ WVD EH KRJ D (ϕ9  LUiQ WRWW JUiI DNNRU pV FVDN DNNRU HU{VHQ |VV]HIJJ{ KD D FV~FVRN KDOPD]iQDN EiUPHO :9: SDUWtFLyMiUD D KH] WDUWR]y LUiQ WiV QpONOL JUiI PHJIHOHO{ V]pWYiJy KDOPD]D WDUWDOPD] OHJDOiEE HJ RODQ pOW PHO :E{O 9EH pV HJ RODW PHO9E{O:EHPHJ %L]RQ WVD EH KRJ KD D  LUiQ WRWW JUiIEDQ D K1 , K2 ,., Kn LUiQ WRWW N|U|N RODQ VRUR]DWD PHOHN N|]O EiUPHO NpW

HJPiVXWiQ N|YHWNH]{QHN YDQ OHJDOiEE HJ N|]|V FV~FVD DNNRU H N|U|N iOWDO PHJKDWiUR]RWWUpV]JUiIMDQHNHU{VHQ|VV]HIJJ{ 11; Bizonyítsa be, hogy ha valamely egyszerû gráf nem teljes, akkor OHJDOiEE HJIpOH PyGRQ OHKHW  ~J LUiQ WDQL KRJ D] HUHGPpQO NDSRWW LUiQ WRWWJUiIQHWDUWDOPD]]RQIHV]tW{IiW  (J JUiI OHKHW V]LPPHWULNXV pV WUDQ]LWtY LV XJDQDNNRU QHP UHIOH[tY$GMRQHUUHSpOGiW0LMHOOHP]LD]HO{EELWtSXV~JUiIRNDW"  .RQVWUXiOMD PHJ D]RNDW D * JUiIRNDW PHOHN FV~FVDL D  HJpV] V]iPRN pV X pV Y pOOHO YDQ |VV]H N|WYH KD XY pVX≡YPRG   14; Ha egy összefüggô G gráf nem egyrétûen bejárható ( tehát WDUWDOPD] OHJDOiEE QpJ SiUDWODQ IRN~ FV~FVRW  DNNRU EL]RQ WVD EH KRJ OHJDOiEENpWNO|QE|]{PLQLPiOLVOHIHGpVHYDQ  +D D * |VV]HIJJ{ JUiI PLQLPiOLV OHIHGpVH N GDUDE YRQDODW WDUWDOPD] DKRO N! DNNRU * HJHWOHQ pOpQHN HOKDJiViYDO RODQ  JUiIRW

NDSXQNPHOQHNPLQLPiOLVOHIHGpVHLNNYDJNYRQDODWWDUWDOPD]QDN  %L]RQ WVD EH KRJ HJ |VV]HIJJ{ (XOHUJUiI PLQGHQ HJHV V]pWYiJy KDOPD]D OHJDOiEE NpW pOW WDUWDOPD] WRYiEEi KRJ PLQGLJ SiURV V]iP~pOE{OiOO  (XOHUIRUPXODVtNEHOLJUiIRNV]DEiORVWHVWHN )HOWpWHOH]]N KRJ D .HGYHV 2OYDVyQDN LQWLXWtYH HOpJ SRQWRV pV NRUUHNW IRJDOPD YDQ D VtN J|UEpNU{O EiU NRUUHNW pV NHOO{HQ iOWDOiQRV J|UEH IRJDORPPDO NpV{EE GLIIHUHQFLiOJHRPHWULDL WDQXOPiQDLNEDQ találkozni fognak. Megemlítjük például, hogy egy egyszerû zárt JordanJ|UEH NpW GLV]MXQNW WDUWRPiQUD ERQWMD D VtNRW 3pOGiXO HJ RULJy N|]pSSRQW~ U VXJDU~ . N|U 3 U VLQ W U FRV W  HJ D] RULJyW WDUWDOPD]y N|UODSUD pV D] D]W N|UO|OHO{ YpJWHOHQ WDUWRPiQUD ERQWMD D VtNRW (J * JUiIRW VtNED UDM]ROKDWyQDN PRQGXQN KD D JUiI pOHLW OHKHW UHDOL]iOQL D VtNEDQ RODQ YRQDODNNDO KRJ EiUPHO NpW pOQHN FVDN D * JUiI

FV~FVSRQWMDLEDQOpY{YpJSRQWMDLOHKHWQHNN|]|VHN 7pWHO %iUPHO * YpJHV JUiI UHDOL]iOKDWy D KiURP GLPHQ]LyV HXNOLGHV]LWpUEHQ %L]RQ WiV/HJHQDGRWWD G ( E , ϕ ,V ) JUiI9HJQNIHODWpUEHQHJH HJHQHVWD]HJHQHVHQ n = V SiURQNpQWNO|QE|]{ Vi (i = 1,2,., n) SRQWRWpVD] H HJHQHVUH LOOHV]NHG{ q = E  SiURQNpQW NO|QE|]{ Si (i = 1,2,., q )  VtNRW pV PLQGHJLN VtNEDQ Pi (i = 1,2,., q )  SRQWRW RODW PHO QHP LOOHV]NHGLN HUH +D ( ) D]HWpODYLpVDYMSRQWRNDWN|W|WWH|VV]HD]D] ϕ (et ) = vi , v j DNNRUN|VVN |VV]H D 9L SRQWRW 3WYHO HJ X HJHQHV V]DNDVV]DO V 3WW LV 9MYHO N|VVH |VV]H HJ Z V]DNDV] $] H pOW D] HO{EE PHJNRQVWUXiOW 9LE{O 9MEH PHQ{ W|U|WW YRQDO IRJMD UHSUH]HQWiOQL $ NRQVWUXNFLy DODSMiQ QLOYiQYDOy KRJ D] pOHNQHN PHJIHOHO{ W|U|WWYRQDODN FVDN D JUiI FV~FVDLQDN NLMHO|OW 9L SRQWRNEDQWDOiONR]KDWQDN A következôkben olyan egyszerû összefüggô síkbeli gráfokkal IRJODONR]XQN

PHOHN ~Q VRNV]|JKiOyW DONRWQDN 6RNV]|JKiOyW DONRWQDN DEEDQ D] pUWHOHPEHQ KRJ IHOERQWKDWyN RODQ PLQLPiOLV N|U|NUH PHOHN D EHOVHMNEHQ PiU QHP WDUWDOPD]QDN D JUiIQDN VHPPLOHQ SRQWMiW H N|U|NHW IRJMXN WDUWRPiQRNQDN QHYH]QL YDJ RUV]iJRNQDN  $ JUiI PLQGHQ FV~FViQDN IRND QDJREE PLQW NHWW{ EiUPHO pO SRQWRVDQ NpW WDUWRPiQW KDWiURO  +D $IULND WpUNpSpW YHVV]N V]HPJUH V QHP iEUi]ROQiQN 0DGDJDV]NiUW pV /HVRWKRW  D pODIULNDL .|]WiUVDViJ EHOVHMpEHQ  WRYiEEi D] RUV]iJKDWiURNDW pV D WHQJHUSDUWRNDW GHILQLiOMXN pOHNQHN $ JUiI FV~FVSRQWMDLQDN WHNLQWMN D]RQ SRQWRNDW DKRO OHJDOiEE KiURP pO WDOiONR]LN DNNRU HJ VRNV]|JKiOyW NDSXQN (JHJ RUV]iJQDN PHJIHOHO{ PLQLPiOLV DEEDQ PLQLPiOLV N|UW D] pUWHOHPEHQ KRJ EHOVHMH QHP WDUWDOPD]]D D JUiI VHPHOLN FV~FVSRQWMiW WDUWRPiQQDN YDJ QHYH]]QN $] RUV]iJQDN $IULNiW N|UOYHY{ WDUWRPiQW YpJWHOHQ WDUWRPiQQDN QHYH]]N 

7pUNpSpV]HWEHQJDNUDQKDV]QiOWHOMiUiVDV]WHUHRJUDILNXVSURMHNFLy PLNRULVHJGJ|PEpVHJSVtNSRQWMDL N|]|WWOpWHVtWQNHJPHJIHOHOWHWpVW ( 7pWHOH]]N IHO KRJ D G J|PEQN HJ  SRQWEDQ pULQWL D VtNRW $  SRQW iWHOOHQHV SRQWMD OHJHQ (  JRQGROMRQ D GpOL LOO D] pV]DNL VDUNUD  $ VtN YDODPHO 3 SRQWMiQDN J|PEL PHJIHOHO{MpW 3 W PHJNDSMXN KD D 3W (YHO |VV]HN|W{ HJHQHVQHN YHVV]N D * J|PEEHO D PHWV]pVSRQWMiW $ V]WHUHRJUDILNXV SURMHNFLyYDO D VtNRQ iEUi]ROKDWXQN HJ J|PEUH UDM]ROW JUiIRW pV IRUGtWYD HJVtNEDUDM]ROWJUiIRWL]RPRUIPyGRQiEUi]ROKDWXQNDJ|PE|Q 3 2 3 6 /HJHQ D G ( E , ϕ ,V )  JUiI HJ VRNV]|JJUiI pOHLQHN D V]iPiW T FV~FVDLQDNV]iPiWQpVWDUWRPiQDLQDNV]iPiWMHO|OMHW 7pWHO (XOHUIRUPXOD +D*VRNV]|JJUiIDNNRU () QTW  $IHQWLWpWHOWV]RNiV(XOHUIpOHSROLpGHUWpWHOQHNLVQHYH]QLPLYHO D KiURPGLPHQ]LyV WpU SROLpGHUHLQHN FV~FVSRQWMDLQDN pOHLQHN pV

KDWiUROy ROGDO ODSMDLQDN D V]iPD N|]|WW iOODStW PHJ |VV]HIJJpVW $ SROLpGHU IRJDOPiQDNW|EEGLPHQ]LyViOWDOiQRVtWiViYDOpVDSROLpGHUHNLQYDULiQVDLQDN DPHJKDWiUR]iViYDOIRJODONR]LNW|EEHNN|]|WWDNRPELQDWRULNXVWRSROyJLD %L]RQ WiV $ * JUiI WDUWRPiQDLQDN V]iPD V]HULQWL WHOMHV LQGXNFLyYDO EL]RQ WXQN +D D * HJHWOHQ HJ N|UE{O iOO DNNRU D WDUWRPiQRN V]iPD  $] pOHN pV FV~FVRN V]iPD PHJHJH]LN H]pUW D W  HVHWpQD]iOOtWiVLJD]/HJHQD]iOOtWiVLJD]W NUDLJD]VEL]RQ WVXN KRJ LJD] W NUH LV +D DGRWW D * JUiI W WDUWRPiQQDO DNNRU W WDUWRPiQQDO UHQGHONH]{ *  JUiIRW RO PyGRQ NDSXQN KRJ YDODPHO WDUWRPiQWHJYYRQDOODONpWWDUWRPiQUDERQWXQN $ YRQDOYNH]G{pVYVYpJSRQWMDD*QHNLVSRQWMDYROW H]IHOWHKHW{ Y WyOYVLJV~MFV~FVSRQWpVV GDUDE ~M pO YDQ * UH YRQDWNR]yODJ HNNRU Q QVW WT TV pV D] LQGXNFLyV IHOWHYpV PLDWW HNNRU n − q + t = 2 $] iEUiQV]DJDWRWW YRQDOODO D]

~M pOHNHW pV UHV N|U|NNHO MHO|OWN D] ~M SRQWRNDW /HJHQDGRWWDVtNRQNpWSiUKX]DPRVHJHQHVHpVI/HJHQYYYH HJPiVXWiQN|YHWNH]{SRQWMDpVIQHNKiURPSRQWMDXXX$YYY SRQWRNDW Ki]DNQDN V D] XXX SRQWRNDW NXWDNQDN QHYH]]N $]W D * JUiIRW PHOQHN D FV~FVDL D] HO{EEL NXWDN LOO Ki]DN pV EiUPHO NXWDW  EiUPHO Ki]]DO pO N|W |VV]H D KiURPKi]KiURPN~W JUiIQDN PRQGXQN*UiIRNVtNEDUDM]ROKDWyViJiWQHPEHIROiVROMDKDYDODPHOpON|Q HJ ~M PiVRGIRN~ FV~FVSRQWRW YHVV]QN IHO YDJ KD YDODPHO NpW pOpW D JUiIQDN DPHOHN XJDQ DUUD D Y PiVRGIRN~ FV~FVUD LOOHV]NHGWHN HJEHROYDVV]XN V YW W|U|OMN $] HO{EEL NpW WUDQV]IRUPiFLyW Ki]L használatra, nevezzük topológikus bôvítésnek illetve szûkítésnek. HILQtFLy$*JUiIRWD JUiIIDOWRSROyJLNXVDQL]RPRUIQDNPRQGMXN ha G-bôl véges sok topológikus szûkítéssel ill. bôvítéssel G-el izomorf JUiIiOOtWKDWyHO{ 7pWHO  *

.XUDWRZVNL   $ * JUiI DNNRU pV FVDN DNNRU VtNED UDM]ROKDWy KD QLQFV RODQ UpV]JUiIMD DPHO WRSROyJLNXVDQ L]RPRUI D] |WV]|JSRQW~.WHOMHVJUiIIDOYDJDKiURPKi]KiURPN~WJUiIIDO $ . V D  JUiIRNDW D IHQWL WpWHO NDSFViQ XUDWRZVNLIpOH JUiIRNQDN LV V]RNWiN QHYH]QL $ WpWHOW QHP EL]RQ WMXN $] (XOHU IRUPXOiEyO VHJtWVpJpYHO D]RQEDQ N|QQHQ EL]RQ WKDWy KRJ D .XUDWRZVNL IpOHJUiIRNQHPVtNEDUDM]ROKDWyN 7pWHO$.XUDWRZVNLIpOHJUiIRNQHPUDM]ROKDWyNVtNED DNNRU %L]RQ WiV $] (XOHUIRUPXOD V]HULQW KD . VtNED UDM]ROKDWy W TQ  W TQ   )LJHOHPEHYpYHKRJ.HJHJWDUWRPiQiWOHJDOiEEpOKDWiUROMD pV PLQGHQ pO SRQWRVDQ NpW WDUWRPiQQDN D KDWiUD HNNRU W≤T HJHQO{WOHQVpJQHNNHOOHQHWHOMHVHGQLDPLLWW ! PLDWWQHPLJD]. UyOWXGMXNKRJSiURVJUiIVH]pUWQLQFVRODQN|UHPHOSiUDWODQ VRN pOW WDUWDOPD]QD H]pUW . WDUWRPiQDLW  D WDUWRPiQRN KDWiUDL N|UW

DONRWQDN OHJDOiEEpOKDWiUROMD$]HO{EELHNDODSMiQ.pOHLQHNDV]iPD DOXOUyOEHFVOKHW{  W  HO V H] HOOHQWPRQG DQQDN KRJ .QDN FVDNpOHYDQ 6tNED UDM]ROKDWy * JUiIRNKR] VRN HVHWEHQ KDV]QRV KR]]iUHQGHOQL HJ *  GXiOLV JUiIRW D N|YHWNH]{ PyGRQ  PLQGHQ 7L WDUWRPiQiEDQ IHOYHV]QN HJXLSRQWRW/HJHQHVRODQpOH*QHNPHOD7L7MWDUWRPiQRN KDWiUiQ IHNV]LNHNNRUYH]HVVHQHV pOXLEyOXMEH*DNRUOiVFpOMiEyODMiQOMXND .HGYHV 2OYDVyQDN UDM]ROMD OH D V]DEiORV KDWV]|J JUiIMiQDN GXiOLViW 0HJHPOtWMN LWW PpJ KRJ KD D N pO iOWDO KDWiUROW WDUWRPiQRN V]iPiW ϕN YDO MHO|OMN DNNRU HJUpV]W ϕ   PLYHO VRNV]|J JUiIRNQiO NL]iUWXN D KXURNpOHNHW PiVUpV]W   2T = 2 ⋅ ϕ 2 + 3 ⋅ ϕ 3 + 4 ⋅ ϕ 4 + . + N ⋅ ϕ N 2 +   6]DEiORVSROLpGHUHN $ KiURPGLPHQ]LyV HXNOLGHV]L WpUEHQ D]RNDW D NRQYH[ SROLpGHUHNHW V]RNWiN V]DEiORVQDN QHYH]QL PHOHNQHN D] pOHL pOV]|JHL pV ODSV]|JHL

HJHQO{HN$SROLpGHUpOHLpVFV~FVDLRODQ*V]DEiORVVtNJUiIRWDONRWQDN  D] KRJ VtNED UDM]ROKDWyDN D V]WHUHRJUDILNXV SURMHNFLyYDO OiWKDWy EH  PHO JUiIQDN PLQGHQ FV~FVSRQWMiQDN D IRND HJHQO{  HJHQO{ SpOGiXO U UHO pV PLQGHQ WDUWRPiQW XJDQDQQL PRQGMXN K pO KDWiURO 7RYiEEi * GXiOLVD *  LV V]DEiORV -HO|OMH D  V]DEiORV SROLpGHU FV~FVDLQDN pOHLQHNWDUWRPiQDLQDNDFV~FVRNIRNV]iPiWpVDWDUWRPiQRNDWKDWiUROy pOHN V]iPiW UHQGUH QTW UK KDVRQOyDQ  *  PHJIHOHO{ DGDWDL OHJHQHN UHQGUH Q T W U K  $ * JUiI pOHL pV D FV~FVSRQWRN IRNV]iPDL N|]|WW WHOMHVOD L T UQWRYiEEiUQ KW TW pV WW NLIHMH]YH L E{O DGyGLN T  UQ pV W UK Q +HOHWWHVtWVNTWLOOHWYHWWD] () (XOHUIRUPXOiED$]WNDSMXNKRJ LL Q>  UK   U@  YDJKYDOYpJLJV]RUR]YD LLL Q>KUUK@ K PLYHOQpVKSR]LWtYHJpV]HNH]pUWtUKDWy LY KUKU!LOO Y KUKU Y WV]RU]DWWiDODNtWYDpVUHQGH]YHQHUMN YL  K U

 $ YL  HJHQO{WOHQVpJQHN K pV U SR]LWtY HJpV] YROWD PLDWW FVDN YpJHV VRN PHJROGiVDYDQ9DQQDNRODQPHJROGiVRNPHOHNKH]WDUWR]yJUiIRNV]iPXQNUD JHRPHWULDL RNRN PLDWW pUGHNWHOHQHN 3pOGiXO KD U  DNNRU D JUiI PLQGHQ V]|JSRQWMiEDQNpWpOWDOiONR]LND]D]D*JUiIN|UKDK DNNRU FV~FVRN V]iPD  pV D * HNNRU D NpW V]|JSRQWEyO V D] D]RNDW |VV]HN|W{ WHWV]{OHJHV V]iP~ pOE{O iOO $] pUGHNHV HVHWHNHW D N|YHWNH]{ WiEOi]DWED IRJODOWXN |VV]H  5      K      Q      T      7      WtSXV WHWUDpGHU NRFND GRGHNDpGHU RNWDpGHU LNR]DpGHU A szabályos testek elég régóta ismertek. Platón Timaeus c mûvében IHOVRUROMD D] |VV]HV V]DEiORV SROLpGHUW $ N|YHWNH]{ iEUiN D V]DEiORV WHVWHNHWpVVtNEDUDM]ROWJUiIMDLNDWPXWDWMiN NRFND WHWUDpGHU GRGHNDpGHU RNWDpGHU LNR]DpGHU   Mátrix reprezentációk Az illeszkedési mátrix HILQtFLy$ G ( E , ϕ ,V )

LUiQ WiVQpONOLJUiILOOHV]NHGpVL LOO LQFLGHQFLD PiWUL[D An ,m ai , j  DKRO DLM  KD D YL FV~FV LOOHV]NHGLND]HMpOUHpVHJpENpQWKDD]HMpOKXURNpOD MRV]ORSPLQGHQHOHPH di  e1 e2  v1  0 1 v2  0 1  v3  0 0 A = v4  0 0  v5  0 0 v6  0 0  v7  0 0  v8  0 0 e3 e4 e5 e6 e7 e8 e9 e10 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 e11   0 0  0 0  0 1  0  1 $IHQWLGHILQtFLyEDQDFV~FVRNV]iPiWQD]pOHNV]iPiWP MHO|OWH D]D] 9 Q pV ( P +XURNpOHNU{O QHP DG KDV]QiOKDWy LQIRUPiFLyW D JUiI LOOHV]NHGpVL e1 e9 PiWUL[D ,UiQ WDWODQ v3 JUiIRN LOOHV]NHGpVL v1 PiWUL[DLQDN D VRUDL LOO D] e3 e10 RV]ORSDLQDN D v8 e4 SHUPXWiOiViYDO e2 e11 HJPiVED iWYLKHW{N +D D e6 e8 JUiIRN * pV D  v7 v6 L]RPRUIDN DNNRU D] e7 v2 v5 v4 e5 LOOHV]NHGpVL PiWUL[DLN $ LOO $ D VRUDLN

LOO RV]ORSDLN DONDOPDV SHUPXWiOiViYDO HJPiVED iWYLKHW{N +D D PiWUL[RN HJIRUPiN DNNRU QHP WXGMXN KRJ D PHJIHOHO{JUiIRNL]RPRUIDNHPLYHOD]LOOHV]NHGpVLPiWUL[QHP DG IHOYLOiJRVtWiVW DUUyO KRJ HJ KXURNpO PHOLN FV~FVSRQWUD LOOHV]NHGLN pV PHOLNUH QHP $ WRYiEELDNEDQ FVDN RODQ LUiQ WDWODQ JUiIRN LOOHV]NHGpVL PiWUL[DLUyO EHV]pOQN PHOHNQHN QLQFV KXURNpON $ GHILQtFLy DODWWL PiWUL[ D V]|YHJEH UDM]ROW JUiI LOOHV]NHGpVL PiWUL[D $ PiWUL[  EORNNEyO iOO PLYHO D JUiIXQN NpW NRPSRQHQVH YDQ pV HO{V]|U D] HOV{ NRPSRQHQVEH WDUWR]y FV~FVRNDW LOO pOHNHW DGWXN PHJ ÈOWDOiEDQ LV LJD] KD YDODPHO * JUiI N NRPSRQHQVE{O iOO DONDOPDV PyGRQ LQGH[HOYH D * FV~FVDLW pV RV]ORSDLW D]  LOOHV]NHGpVL PiWUL[D N EORNNEyO IRJ iOOQL D]D] D PiWUL[D D]  A1 0 . 0    0 A2 . 0   DOiEEL DODN~ OHV] A =  DKRO D] $L D * PiWUL[ L  . .    0 . An   0

NRPSRQHQVpQHND]LOOHV]NHGpVLPiWUL[D 7pWHO +D D * JUiI UHQGMH Q pV N NRPSRQHQVE{O iOO pV LOOHV]NHGpVLPiWUL[D$DNNRUUJ $ QN DPiWUL[RWD=WHVW I|O|WWLQHNWHNLQWMN D]D]PRG  V]iPROXQN  %L]RQ WiV $ EL]RQ WiVW D NRPSRQHQVHN V]iPD V]HULQWL WHOMHVLQGXNFLyYDOYpJH]]N/pQHJpEHQDWpWHOHO{WWHPOtWHWW EORNNIHOERQWiVPLDWWHOHJHQG{D]iOOtWiVWN HVHWpQEHOiWQL PLYHODI{iWOyQNtYOPLQGHQWWiOOpVHPLDWWDEORNNRNEyO iOOy KLSHUPiWUL[ UDQJMD PHJHJH]LN D I{iWOyEDQ iOOy EORNN UDQJMDLQDN |VV]HJpYHO /HJHQ * HOV{ NRPSRQHQVH QHN pV OHJHQ FV~FVDLQDN V]iPD Q V LOOHV]NHGpVL PiWUL[D $ $] $ PiWUL[UDQJMDOHJIHOMHEEQOHKHW9DOyEDQDGMXND]$PiWUL[ PLQGHQ VRUiW D] $ PiWUL[ XWROVy VRUiKR] (NNRU D] XWROVy VRU PLQGHQ HOHPH  OHV] PLYHO PLQGHQ RV]ORSEDQ  GDUDE HJHV YDQ  HJ pO SRQWRVDQ NpW FV~FVUD LOOHV]NHGLN +D QQpO NHYHVHEE V VRU |VV]HJH LV W DGQD SpOGiXO D] LLLV 

DNNRU YYYVFV~FVRNHJLNpE{OVHPYH]HWQHpOYDODPHOPiVLND YYYV SRQWRNWyO NO|QE|]{ FV~FVSRQWED HOOHQWPRQGYD DQQDN KRJ * |VV]HIJJ{ YROW $] HO{EE PRQGRWWDN PHJLVPpWHOKHW{N * EiUPHO NRPSRQHQVpUH YRQDWNR]yODJ V ILJHOHPEH YpYH KRJ D VSHFLiOLV DODN~ $ KLSHUPiWUL[XQN $L EORNNMDLQDN UDQJMDLQDN D] |VV]HJH PDJiQDN D KLSHUPiWUL[QDN D UDQJMiYDOHJH]LNPHJD]iOOtWiVWEHEL]RQ WRWWXN +D D * JUiI $ LOOHV]NHGpVL  PiWUL[iEyO NRPSRQHQVHQNpQW HJHJ VRUW HOKDJXQN DNNRU * ~Q UHGXNiOW LQFLGHQFLD PiWUL[iW NDSMXN 1HP QHKp] EHOiWQL KRJ KD YDODPHO NYDGUDWLNXV QN ⋅ QN DVUpV]PiWUL[GHWHUPLQiQVDQHPDNNRU D UpV]PiWUL[ RV]ORSDLKR] WDUWR]y pOHN * PLQGHQ NRPSRQHQVpQHN NLMHO|OLNHJHJIHV]tW{IiMiW 7pWHO+DD*JUiIHHHNpOHLN|UWDONRWQDNDNNRU D] LQFLGHQFLD PiWUL[ D UHGXNiOW LQFLGHQFLD PiWUL[ HHHNiOWDONLMHO|OWRV]ORSDLOLQHiULVDQIJJ{N %L]RQ WiV $ NLMHO|OW RV]ORSRNQDN

PHJIHOHO{ pOHN N|]O NHWW{YDJLOOHV]NHGLNEiUPHOFV~FVSRQWUDH]pUWDNLMHO|OW RV]ORSRN EiUPHO VRUiEDQ  YDJ  GDUDE HV iOO  V H]HN |VV]HJHPRG  YDOyEDQ$]D]DV]yEDQIRUJyYHNWRURN|VV]HJH VH]SRQWRVDQD]WMHOHQWLKRJOLQHiULVDQIJJ{N HILQLFLy $ G ( E , ϕ ,V )  LUiQ WRWW JUiI LOOHV]NHGpVL PiWUL[iQDNQHYH]HPD] An , m ai , j DKRODLM KDDYLFV~FVEDIXW ( )  EH D] HM pO DLM  KD YL FV~FVEyO IXW NL D] HM pO pV  HJpENpQWKDD]HMpOKXURNpODMRV]ORSPLQGHQHOHPH ËUiQ WRWWJUiILQFLGHQFLDPiWUL[iUDLVKDVRQOyiOOtWiVRN LJD]ROKDWyN PLQW DPLOHQHNHW D] tUiQ WiV QpONOL JUiIRNUD LJD]ROWXQN GH +3RLQFDUH DOiEEL WpWHOH UiYtOiJtW EL]RQRV HOWpUpVHNUH 7pWHO +D D] $ NYDGUDWLNXV PiWUL[ YDODPHO * JUiI LQFLGHQFLD PiWUL[iQDN QHP QXOOD GHWHUPLQiQV~ UpV]PiWUL[D DNNRU GHW $  %L]RQ WiV 7HUPpV]HWHVHQ LWW D YDOyV WHVW I|O|WW V]iPROWXN D GHWHUPLQiQVW /HJDOiEE HJ RV]ORS YDQ D

V]yEDQ IRUJyGHWHUPLQiQVEDQDPHOEHQFVDNHJHOHPNO|QE|]LNWyO fejtsük ki e sor szerint, és az eggyel alacsonyabb rendû DOGHWHUPLQiQVUD LVPpWHOMN PHJ D] HO{EEL RNRVNRGiVW (]W D] HOMiUiVW PHJLVPpWHOYH DQQLV]RU PLQW DPHQQL D GHWHUPLQiQV UHQGMHYpJH]HWODEL]RQ WDQGyiOOtWiVDGyGLN A körmátrix $ . (NL,M )  N|UPiWUL[ D]W PXWDWMD KRJ D G ( E , ϕ ,V )  JUiI pOHL PHO N|U|NEHQ V]HUHSHOQHN HILQLFLy V]HULQW 1, ha e j é le a ki körnek ki , j =  ki körnek . 0, ha ej nem é le a ,UiQ WRWW * JUiIKR] KD PLQGHQ N|UK|] PiU NLMHO|OWQN HJHJEHMiUiVLLUiQWDNNRUD]DOiEELXWDVtWiVVDOUHQGHOQN N|UPiWUL[RW  1, ha e é le a k körnek é s irá nyuk egyezô j i   ki , j = −1 ha e j é le a ki körnek é s irá nyuk különbözô      0, ha e j nem é le a ki körnek )HOtUMXN D] DOiEEL LUiQ WRWW LUiQ WDWODQ  JUiI .  N|UPiWUL[iW )ROWRQRV YRQDOODO UDM]ROWXN D * JUiI ) IHV]LW{ IiMiQDN

IDYi]iQDN pOHLW Y Y H H H H Y H H Y H Y H H  $ N|U|N LOO pOHN VRUUHQGMpW D] DOiEEL V]DEiO V]HULQW DGMXN PHJ .LMHO|OMN D * JUiI HJ ) IDYi]iW  KD  QHP YROW |VV]HIJJ{ DNNRU PLQGHQ HJHV NRPSRQHQVpQHN PHJDGMXN HJ IDYi]iW (O{V]|UD])IiUDYRQDWNR]yHLN|W{pOHNHWLQGH[HOMN  LWW LYHO  pV D] iOWDOXN PHJKDWiUR]RWW N|U|NHW NLYHO ,WW MHJH]N PHJ KRJ D * JUiI ) IDYi]iUD YRQDWNR]yDQ D] H pO N|W{pOKDQHPpOH)QHN$*JUiI)IHV]tW{IiMDpVHN|W{pOH egyértelmûen meghatározza G-nek egy k körét, mivel F maximális |VV]HIJJ{ N|UW QHP WDUWDOPD]y UpV]JUiIMD YROW *QHN ËUiQ WRWW JUiIRN HO{EE HPOtWHWW DODSN|UHLW )UH YRQDWNR]y N|W{pOHLQHNPHJIHOHO{HQtUiQ WMXN 1  0 0  0 0  1 K1 =  1  1  0 0  0 1  0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 1 0 0

1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0   0 0 1 0 0 0 0 1 0 0   0 0 0 0 1  0 0 0 0 0   0 1 1 0 0  0  K2 =  −1 0 1 0   1 0 0 1 0   0 0 1 1 0  0 −1 0 1 0   0  0 0 1 −1  1 0 −1 1 0    0 1 1 −1 0 0 1 −1 0 0  0 −1 1 0 0 0 1 0 1 0  0 0 1 1 0 1 0 0 0 0  1 0 0 0 0 0 0 1 1 0  0 1 0 1 0  0 0 1 1 0 0 1 0 1 0  0 1 −1 0 0 0 0 0 0 0  0 0 0 0 0 ËUMXNIHODNRUiEEDQOHUDM]ROW*LOO tUiQ WRWWJUiI LOOHV]NHGpVL$LOO$PiWUL[iWLV 1  1 A1 =  0  0  0 1 1 0 0 0 1 0 0 1 0  −1 1 −1 0   1 −1 0 −1 A2 =  0 0 0 0  0 0 1 1  0 0 0 0 LV 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0  0 0   1  1 0 1 0 0 0  0 0 1 0 0 0 −1 −1 1 0    0 0 0 −1 1   0 0 0 0 −1

9HJN pV]UH KRJ $ .7 1  ]pUXV PiWUL[ pV $ %7 1  7pWHO +D $ * JUiIQDN D] $ LOOHV]NHGpVL LOOHWYH . N|UPiWUL[iQDN RV]ORSDL XJDQD]RQ pOVRUR]DW V]HULQW  UHQGH]HWWHNDNNRU$ .7 1pV $7 1 PRG  ]pUXVPiWUL[RNDWMHO|O   LWW1pV1LV %L]RQ WiV$]LUiQ WiVQpONOLHVHWHWWiUJDOMXNpVRWW LV FVDN D] HOV{W PLYHO DEEyO D PiVRGLN WUDQV]SRQiOiVVDO PHJNDSKDWy+DD]$DLVRUiKR]WDUWR]yYLFV~FVQHPLOOHV]NHGLN D NM N|UUH DNNRU D  V]RU]DWPiWUL[ QLM HOHPH  PLYHO D YLUH LOOHV]NHG{pOHNQHPpOHLDNMN|UQHN+DD]$DLVRUiKR]WDUWR]y YL FV~FV LOOHV]NHGLN D NM N|UUH DNNRU D  V]RU]DWPiWUL[ QLM HOHPH  PLYHO D YLUH LOOHV]NHG{ pOHN N|]O SRQWRVDQ  pOH D NMN|UQHN A csúcsmátrix ,UiQ WRWW pV LUiQ WiV QpONOL JUiIRN HVHWpQ HJIRUPiQ GHILQLiOKDWMXN D FV~FV  YDJ V]RPV]pGRVViJL  PiWUL[RW $ PiWUL[ DLM HOHPH D]RNQDN D] pOHNQHN D V]iPiYDO HJH]LN PHJ

DPHOHNYLE{OIXWQDNYMEHWHUPpV]HWHVHQKDD]HpOLUiQ WiV QpONOL pV ϕ (H) = Y LY M = Y MY L  DNNRU ~J WHNLQWMN KRJ H YL E{OPHJYMEHpVIRUGtWYDLVD]D]HYME{OPHJYLEH$]D]Q FV~FVSRQW~ LUiQ WiV QpONOL * JUiI FV~FVPiWUL[D V]LPPHWULNXV Q QHVNYDGUDWLNXVPiWUL[+DDGRWW$* (ϕ9 JUiIpV 9 Q akkor csúcsmátrixa n*n-es valós elemû mátrix. ( ) ( ) ( ) HILQLFLy $ * (ϕ9  JUiIQDN Vn n = ai , j  FV~FVPiWUL[D KD ai , j = ∑1 ( ϕ ( e ) = vi , v j )  3pOGDËUMXNIHOD]DOiEELtUiQ WRWWJUiIV]RPV]pGRVViJL YDJDGMHFHQFLDPiWUL[iW  Y v1  0 0 0 0 0 0 0 0   Y v2  1 0 0 0 0 0 0 0 v 3  0 1 0 1 1 0 0 0   Y r Y v 4  0 0 0 0 1 0 0 0 Y Y Y V =   eUGHPHV v5 0 1 0 0 0 0 0 0   v 6  0 0 0 0 0 0 1 1 v 7  0 0 0 0 0 0 0 2   v8  0 0 0 0 0 0 0 0 PHJMHJH]QL KRJ D FV~FVPiWUL[ D KXURNpOHNU{O LV LQIRUPiO

7RYiEEiKDD*JUiIFV~FVDLW$PyGRQLQGH[HOYHFV~FVPiWUL[D r r 9 $   LOO % PyGRQ LQGH[HOYH 9%  DNNRU D VRURN pV D] RV]ORSRN DONDOPDVFVHUpMpYHOHOpUKHW{KRJD]HJLNPiWUL[RWiWYLVV]N Y  D PiVLNED 0LYHO XJDQD]RNDW D VRURNDW pV RV]ORSRNDW NHOO IHOFVHUpOQL H]pUW YDQ RODQ 3 SHUPXWiFLy PiWUL[ PHOUH r r 9$ = 3 −19%3 $IHQWLHNEHQOpQHJpEHQEHOiWWXNDN|YHWNH]{WpWHOW 7pWHO +D D * JUiIQDN D FV~FVPiWUL[D $ pV D  JUiIQDN FV~FVPiWUL[D % DNNRU D * pV D  PiWUL[RN L]RPRUILiMiQDN V]NVpJHV pV HOpJVpJHV IHOWpWHOH D] KRJ OpWH]]pN RODQ 3 SHUPXWiFLyPiWUL[PHOUHWHOMHVOKRJ $ = 3 −1%3  $ FV~FVPiWUL[ KDWYiQDLUyO QHP QHKp] EHOiWQL D] DOiEEL WpWHOW ( ) r n r 7pWHO/HJHQD*JUiIFV~FVPiWUL[D9 $  V A QHNY LQ,M HOHPH PHJDGMD * YL pV YM pOVRUR]DWRNQDNDV]iPiW FV~FViW |VV]HN|W{ LUiQ WRWW %L]RQ WiV7HOMHVLQGXNFLyYDO EL]RQ WXQN Q  HVHWpQ D]

iOOtWiVDGyGLNDFV~FVPiWUL[GHILQLFLyMiEyO7HJJNIHOKRJ Q PUH LJD] D] iOOtWiV pV LJD]ROMXN P UH -HO|OMH vi(,k )  D] LQGXNFLyV IHOWHYpV V]HULQW D]RQ P KRVV]~ViJ~ LUiQ WRWW pOVRUR]DWRN V]iPiW PHOHN D] L FV~FVRW D N FV~FFVDO N|WLN m |VV]H 7RYiEEi MHO|OMH vk( ,)j  D] N FV~FVRW D M FV~FFVDO 1 |VV]HN|W{pOHNV]iPiW$ vi(, k ) ⋅ vk( ,)j V]RU]DWPHJDGMDD]LFV~FVEyO D M FV~FVED YH]HW{ RODQ LUiQ WRWW P KRVV]~ViJ~ pOVRUR]DWRN V]iPiW PHOHN D N SRQWUD LOOHV]NHGQHN   PLNRU m 1 1 m LV N M V]RPV]pGMD  N V]HULQW |VV]HJH]YH D vi(, k ) ⋅ vk( ,)j V]RU]DWRNDW PHJNDSMXN D] L FV~FVEyO D M FV~FVED YH]HW{ k =n 1 m+1 m LUiQ WRWW pOVRUR]DWRN V]iPiW PiVUpV]U{O vi(, j ) = ∑ vi(, k ) ⋅ vk( ,)j  DPL k =1 QHPPiVPLQWDFV~FVPiWUL[ P KDWYiQiQDNLMHOHPH ( ) r ,0HJMHJ]pV+DYDODPLOHQQUH V A n DNNRUDJUiIQHP WDUWDOPD]KDWtUiQ WRWWN|UW ,,0HJMHJ]pV$FV~FVPiWUL[ MyO

DONDOPD]KDWy YDODPHO $ KDOPD]RQ DGRWW ρ ELQiULV UHOiFLy WXODMGRQViJDLQDN D MHOOHP]pVpUH$*ρ (ϕ9 JUiIRWDN|YHWNH]{PyGRQUHQGHOMND] $KDOPD]RQDGRWWρELQpUUHOiFLyKR] L *FV~FVSRQWMDL$HOHPHLOHV]QHND]D]$ 9 ( ) ( ) LL  e = ( vi , v j ) ∈ E ⊆ ( A ⊗ A) ⇔ vi ρv j PiVV]yYDOYLWYMYHO DNNRU pV FVDN DNNRU N|WL pO |VV]H KD YL ρ UHOiFLyEDQ iOO YM YHO $ ρ ELQpU UHOiFLy DNNRU pV FVDN DNNRU UHIOH[tY KD r Gρ ( E , ϕ ,V )  JUiI V A  FV~FVPiWUL[iQDN I{iWOyMiEDQ PLQGHQWW  iOO  $ ρ ELQpU UHOiFLy DNNRU pV FVDN DNNRU V]LPPHWULNXV KD r Gρ ( E , ϕ , V ) JUiI V A FV~FVPiWUL[DV]LPPHWULNXV Matroidok $ PDWURLGHOPpOHWHW +DVVOHU :KLWQH DODSR]WD PHJ D lineáris függõség algebrai elméletét vizsgáló 1935-ös dolgozatával. Az elmúlt 62 esztendõben több könyv is megjelent H WiUJN|UEHQ $ PDWURLGHOPpOHW VRN DONDOPD]iVUD WDOiOW D] iUDPN|U|N DQDOt]LVpEHQ NDSFVROiV

HOPpOHWEHQ OLQHiULV SURJUDPR]iVEDQKiOyHOPpOHWEHQpVJUiIHOPpOHWEHQ HILQtFLy $] 0 ( ,  UHQGH]HWW SiUW PDWURLGQDN nevezzük, ha rendelkezik a következõ tulajdonságokkal, E véges KDOPD]pV, rendelkezik a következõ tulajdonságokkal:   ∅ ∈ , D]D]D]UHVKDOPD]HOHPH,QHN   KD [∈ , pV ⊆[ DNNRU ∈,QHN D]D] , EiUPHO [ HOHPpQHNEiUPHOUpV]KDOPD]DLVPpWHOHPH,QHN   KD ,S,S∈ , QHN pV ,S ,S DNNRU  ∃[ ∈ , S+ ( ) RODQ KRJ , S ∪ {[ } ∈ ,   H GHILQtFLyQiO D] ,  pV , XJDQD]W MHOHQWL  3pOGiN L  /HJHQ * (ϕ, V) egy egyszerû gráf és , MHO|OMH  ( pOHLQHN RODQ UpV]KDOPD]DLW DPHOHN *QHN N|UPHQWHV UpV]JUiIMDLWMHO|OLNNLHNNRUD] (, SiUUHQGHONH]QLIRJD PDWURLGRNWyOPHJN|YHWHOWWXODMGRQViJRNNDO LL  /HJHQ (  D]  0 PiWUL[ RV]ORSYHNWRUDLQDN D KDOPD]D D]D] ( ^ PPP PMPV`  ( OLQHiULVDQ IJJHWOHQ RV]ORSYHNWRUDLQDN D KDOPD]iW MHO|OMN , YHO

HNNRU D] ( , SiUPDWURLGRWDONRW $]RNDW D] 0 ( ,) matroidokat, amelyeknél E tekinthetõ YDODPHO * JUiI pOHL KDOPD]iQDN pV  ,  HOHPHL D  N|UPHQWHV UpV]JUiIMDLpOHLKDOPD]iQDNJUDILNXVPDWURLGRNQDNPRQGMXN $]RNDW D] 0 ( ,) matroidokat, amelyeknél E tekinthetõ YDODPHO PiWUL[ RV]ORSYHNWRUDL KDOPD]iQDN pV , D IJJHWOHQ RV]ORSYHNWRURN KDOPD]iQDN D KDOPD]DNpQW PiWUL[PDWURLGQDN PRQGMXN $ PDWURLGHOPpOHW VRN HOQHYH]pVW IRJDOPDW YHWW iW D lineáris algebrából ill. a gráfelméletbõl Kedves Olvasónknak ezekbõl nyújtunk át egy csokorra valót. Kicsit ömlesztve  mellõzve ez egyszer a formákat, reméljük ez nem vezet IpOUHpUWpVUH $] , HOHPHLW IJJHWOHQ KDOPD]RNQDN QHYH]]N $] ,KDOPD]%HOHPpWEi]LVQDNQHYH]]NKDPD[LPiOLVDQIJJHWOHQ Itt a maximális jelzõ nyilván abban az értelemben értendõ, KRJ ( EiUPHOLN RODQ $ UpV]KDOPD]iW LV YHJN DPHOLN YDOyGL PyGRQ WDUWDOPD]]D %W %⊂$   DNNRU D] $

QHP HOHPH , nek. Az E tetszõleges A részhalmazának a UDQJMiQ U $ Q D] $ PD[LPiOLVDQ IJJHWOHQ UpV]KDOPD]iQDN D] HOHPHLQHN D V]iPiW pUWMN +D ( YDODPHO $ UpV]KDOPD]D QHP HOHPH , QHN DNNRU azt függõnek mondjuk. Az A ( $ ⊆ ( UpV]KDOPD]OH]iUWMiQ YDJ $ iOWDO IHV]tWHWW  D]W D]  VS $  KDOPD]W pUWMN PHOQHN UDQJMDPHJHJH]LN$UDQJMiYDOpVPD[LPiOLV0D[LPiOLVDEEDQD] pUWHOHPEHQ KRJ QHP OpWH]LN RODQ VS $ ¶ KDOPD] PHOQHN D UDQJMD XJDQFVDN PHJHJH]QH $ UDQJMiYDO pV YDOyGL PyGRQ WDUWDOPD]QiVS $ W Egy minimálisan függõ K halmazt N|UQHN QHYH]]QN Minimálisan függõ nyilván abban az értelemben, hogy K-nak semelyik valódi részhalmaza sem lesz függõ, azaz K bármely YDOyGL UpV]KDOPD]D PiU HOHPH , QHN GH PDJD . QHP HOHPH ,  QHN 7pWHO /HJHQ ; < IJJHWOHQ UpV]KDOPD]RN 0EHQ +D ; HOHPHLQHN D V]iPD NHYHVHEE PLQW < HOHPHLQHN D V]iPD D]D] ;  <  DNNRU OpWH]LN RODQ

=⊆<; KRJ ; ∪ = <  pV ;∪= IJJHWOHQ0EHQ %L]RQ WiV/HJHQ= RODQKRJUHQGHONH]]pND]DOiEEL WXODMGRQViJRNNDO  L =⊆<; LL ;∪= IJJHWOHQ0EHQ LLL  +D ; ∪ =  ≥ ; ∪ =  ;∪= IJJHWOHQ 0EHQ pV =⊆<; DNNRU 7HJNIHOKRJOpWH]LNRODQ=KRJ ; ∪ =  < < HNNRU OpWH]LN HJ RODQ <⊆< PHOUH <  ; ∪ =  +  0LYHO < IJJHWOHQ OHKHW DONDOPD] D PDWURLGRN  D[LyPiMiW /pWH]LN ∈<  − (; ∪ =  ) RODQ KRJ ; ∪ =  ∪ {}  IJJHWOHQ 0EHQ GH D =  ∪ {}  OpWH]pVH HOOHQWPRQG LLL QHN (]pUW ; ∪ =  ≥ <  V H]]HO D EL]RQ WiV NpV] .|YHWNH]PpQ $] 0 PDWURLG EiUPHO % Ei]LViQDN D] HOHP V]iPDPHJHJH]LN0UDQJMiYDO  %L]RQ WiV /HJHQ  %   % , akkor az elõzõ tétel V]HULQW OpWH]LN RODQ =⊆ ^ %  % ` RODQ  KRJ =∪ %  IJJHWOHQDPLYLV]RQWHOOHQWPRQG % PD[LPiOLV .|YHWNH]PpQ +D  % 

pV  %  Ei]LVDL 0QHN pV [ ∈ % − %   ( ) DNNRU OpWH]LN RODQ ∈% − %  PHOUH WHOMHVO KRJ % ∪ {} − {[ } Ei]LVD0QHN %L]RQ WiVQpONOPHJHPOtWMN LWW QpKiQ WXODMGRQViJiW D UDQJIJJYpQQHN 7pWHO /HJHQ DGRWW D] 0 [∈(HNNRU ( ,   PDWURLG pV $%⊆( pV   ≤ U($ ) ≤ $  +D$⊆%DNNRUU $ ≤ U %  ( )  U($ ) ≤ U $ ∪ {[ } ≤ U($ ) +  4. Részmoduláris egyenlõtlenség U($ ) + U(% ) ≥ U($ ∪ % ) + U($ ∩ % )  ( ) U($ ∪ {}) +D U $ ∪ {[ } ( ) U $ DNNRU U $ ∪ {[ } ∪ {} U $  Ha az E n elemû halmaz k ( ≤ N ≤ Q) elemû részhalmazainak a KDOPD]iW YiODV]WMXN , QHN DNNRU HJ 0 PDWURLGRW NDSXQN PHOHW XQLIRUP PDWURLGQDN V]RNiV QHYH]QL -HOH 8QN $] 8QQ PDWURLGRW V]DEDG PDWURLGQDN PRQGMXN PLYHO ( EiUPHO UpV]KDOPD]D IJJHWOHQ D] 8Q PDWURLGRW WULYLiOLV PDWURLGQDN QHYH]]NPLYHOFVDND]UHVKDOPD]∅IJJHWOHQEHQQH 1HP QHKp] EHOiWQL

8 QHP OHKHW JUDILNXV PDWURLG PLYHO nincs olyan 4 élû gráf, hogy bármely 3 éle kört alkosson. A körökkel kapcsolatos következõ állítások közvetlenül a GHILQtFLyN|YHWNH]PpQHL  %iUPHON|UEiUPHOYDOyGLUpV]KDOPD]DIJJHWOHQ+D &pV& különbözõ körök, akkor C⊄&  +D&N|UDNNRUU & &  $]0PDWURLGEDQDNNRUpVFVDNDNNRUQLQFVN|UKD( PLQGHQ UpV]KDOPD]D IJJHWOHQ HNNRU 0QHN FVDN HJ Ei]LVD YDQ WLPDJD(  Gráfok színezése $ QyEDQ VRKD QH IHOHGMN NH]G{L PLYROWXQNDW 9HNHUG 7DPiV A színészi hatás eszközei-Zeami mester mûvei szerint, *RQGRODW    R *UiIRN VtNED UDM]ROKDWyViJiUyO EHV]pOYH GHILQLiOWXN D WDUWRPiQ LOOHWYH RUV]iJ  IRJDOPiW 7pUNpSHN V]tQH]pVpQpO V]RNiVRV HOMiUiV D] KRJ V]RPV]pGRV RUV]iJRNDW NO|QE|]{ V]tQHNNHO V]tQH]QHN NL .pW RUV]iJRW V]RPV]pGRVQDN V]RNiV QHYH]QL KD D N|]|V KDWiUXN KRVV]D QiO QDJREE V]iP D]D]

YDQN|]|VpON$*VtNEHOLJUiIRWNV]tQH]KHW{QHNPRQGMXNKD * WDUWRPiQDLW NL OHKHW IHVWHQL N V]tQQHO RO PyGRQ KRJ EiUPHO NpW szomszédos ország különbözô színû +D D] DGRWW VtNED UDM]ROKDWy * JUiI GXiOLVD  DNNRU D  N V]tQQHO YDOy V]tQH]KHW{VpJH * UH YRQDWNR]yODJ D]W MHOHQWL KRJ FV~FVDLW NL OHKHW V]tQH]QL N V]tQQHO RO PyGRQ KRJ V]RPV]pGRV FV~FVRN V]tQHL NO|QE|]{HN $]D] *  EiUPHO pOpQHN két végpontja különbözô színû. A színezési probléma duális JUiIUD YDOy iWIRJDOPD]iVD OHKHW{VpJHW DG DUUD KRJ WHWV]{OHJHVJUiIV]tQH]KHW{VpJpU{OEHV]pOMQN HILQtFLy $ * JUiI NURPDWLNXV V]iPD N KD  FV~FVDL N V]tQQHONLV]tQH]KHW{NGHNHYHVHEEHO N HOPiUQHP EHQ 0|ELXV HJ HO{DGiViEDQ PHJIRJDOPD]WD D QpJV]tQVHMWpVWPHOD]WiOOtWMDKRJEiUPHOVtNEHOLWpUNpS NLV]tQH]KHW{V]tQQHO$VHMWpVWH0RUJDQWHWWHLVPHUWpÐD SUREOpPiW)UDQFL*XWKULHWyOYHWWHiWN|UO&DOH EHQ

MHOHQWHW PHJ HJ GROJR]DWRW D QpJV]tQVHMWpVU{O D 3URF 5RDO *HRJUDSKLFDO 6RFLHW HOV{ N|WHWpEHQ EHQ +HDZRRG HJ .HPSHW{O V]iUPD]y KLEiV EL]RQ WiVW YL]VJiO pV VLNHUO EHEL]RQ WDQLD KRJ VtNJUiIRNQiO |W V]tQ HOHJHQG{ D V]tQH]pVKH]$QpJV]tQVHMWpVUH.$SSHOpV:+DNHQEDQ V]iPtWyJpS IHOKDV]QiOiViYDO DGWDN EL]RQ WiVW %L]RQ WiVXNEDQ D]RQEDQ D]yWD W|EEHQ pV W|EEV]|U LV WDOiOWDN KLEiW GH D]RN MDYtWKDWyQDN EL]RQXOWDN $ PDWHPDWLNXVRN HJUpV]H $ YLWDWMD D]W KRJ HJ WpWHOQHN D % V]iPtWyJpSHV EL]RQ WiVD HOIRJDGKDWy & H $ WRYiEELDNEDQ VtNEHOL JUiIRNUyO V]HUHWQpQN PHJPXWDWQL KRJ |W V]tQQHO PLQGLJ NL V]tQH]KHW{N $]W EHOiWQL KRJ OHJDOiEE  V]tQ szükséges, könnyû. Például a tetraéder síkba rajzolt gráfja FVDNV]tQQHOV]tQH]KHW{NL  +D D * JUiIXQN Y SRQWMD PiVRGIRN~ pV YUH HH LOOHV]NHGHWW  ϕ H XY pV ϕ H YZ  DNNRU YW W|U|OYH pV Y HH pOHN KHOHWW HJ H  pOW

EHYH]HWYH  ϕ H XZ  D V]tQH]pV PyGMD YiOWR]DWODQ PDUDG YLV]RQW D] ~M JUiIXQNEDQ HJJHO NHYHVHEE PiVRGIRN~ SRQW OHV] (OpUKHW{  KRJ RODQ VtNEHOL JUiIRNNDO IRJODONR]XQN DPHOHNQHN QLQFVHQ PiVRGIRN~ FV~FVSRQWMDL +D YDODPHO SRQW IRND QiO QDJREE DNNRU D * JUiIXQNDW iWDODNtWKDWMXN RO PyGRQ KRJ D NLV]tQH]KHW{VpJH QH YiOWR]]pN GH OHJIHOMHEE FVDN KDUPDGIRN~ SRQWMD OHJHQ /HJHQD]DSRQWSpOGiXOD]iEUiQDNPHJIHOHO{HQ|W|GIRN~SRQW 5DM]ROMXQNN|UO|WWHHJ&N|UW6D]DSRQWKHOHWWYH]HVVQN EH~MSRQWRWPHOHNPLQGHJLNHPiUKDUPDGIRN~+DH]XWyEEL JUiI NLV]tQH]KHW{ DNNRU NLV]tQH]KHW{ OHV] D] HUHGHWL LV (OHJHQG{ D]W OiWQL KRJ KD D] ~M JUiI & N|UpW SRQWWi ]VXJRUtWMXN V D N|UW KDWiUROy WDUWRPiQRN V]tQH]pVpW YiOWR]DWODQXOKDJMXNDNNRUDUpJLJUiIQDNHJMyV]tQH]pVpW NDSMXN (]HN V]HULQW VtNEHOL JUiIRN V]tQH]KHW{VpJpW VLNHUOW YLVV]D YH]HWQL DUUD D] HVHWUH PLNRU LV D JUiI PLQGHQ SRQWMD

KDUPDGIRN~ $] DOiEELDNEDQ EHEL]RQ WXQN HJ WpWHOW PHO D]W PRQGMD KRJ EiUPHO VtNED UDM]ROKDWy  JUiIQDN YDQ RODQ WDUWRPiQD PHOHW  YDJ |WQpO NHYHVHEE pO KDWiURO +D VLNHUO PHJPXWDWQXQN KRJ D] |W YDJ |WQpO NHYHVHEE pOOHO KDWiUROW WDUWRPiQRN PLQGLJ HOKDJKDWyN DQpONO KRJ D PHJYiOWR]RWW JUiI V]tQH]KHW{VpJH YiOWR]QD DNNRU YpJH]HWO LV PHJROGRWWXN D] |WV]tQWpWHO EL]RQ WiViW $  ROGDORQ V]HUHSO{   IRUPXOD V]HULQW 2T = 2 ⋅ ϕ 2 + 3 ⋅ ϕ 3 + 4 ⋅ ϕ 4 + . + N ⋅ ϕ N +   DKRO LV T D] pOHN V]iPiW ϕL  D] L GDUDE pO iOWDO KDWiUROW WDUWRPiQRNV]iPiWMHO|OWH+DD*JUiIXQNFV~FVDLQDNDV]iPiW QMHO|OLDNNRU (S 2) 3n = 2 ⋅ ϕ 2 + 3 ⋅ ϕ 3 + 4 ⋅ ϕ 4 +.+ k ⋅ ϕ k +  WRYiEEi PLYHO W D] bg |VV]HV WDUWRPiQ V]iPiW MHO|OWH  6 3 W = ϕ 2 + ϕ 3 + ϕ 4 +. + ϕ N +  6]RUR]]XNPHJDWPDO6WYHOpV6WWDOHNNRU 6T = 6 ⋅ ϕ 2 + 9 ⋅ ϕ 3 + 12 ⋅ ϕ 4 + . +3N ⋅ ϕ N + b6

2g6Q = 4 ⋅ ϕ 2 + 6 ⋅ ϕ 3 + 8 ⋅ ϕ 4 + . +2N ⋅ ϕ N +  b6 3g6W = 6ϕ 2 NDSMXN + 6ϕ 3 + 6ϕ 4 + . +6ϕ N + D & & +D D] HXOHUIRUPXOiW YpJLJV]RUR]]XN WDO DNNRU 12 = 6Q − 6T + 6W DGyGLNVDIHQWL NpSOHWHNHWEHKHOHWWHVtWYH b6 4g12 = 4ϕ 2 + 3ϕ 3 + 2 ϕ 4 + ϕ 5 − ϕ 7 − 2 ϕ 8 − . − (N − 6) ϕ N + DGyGLN $] 6HV IRUPXOD MREE ROGDOiQDN SR]LWtYQHN NHOO OHQQLH H]pUW KDUPDGIRN~ UHJXOiULV JUiIQDN YDQ OHJDOiEE HJ RODQ WDUWRPiQD PHOHW  YDJ QpO NHYHVHEE pO KDWiURO $]D] EHEL]RQ WRWWXNDN|YHWNH]{WpWHOW 7pWHO+DD*JUiIVtNEDUDM]ROKDWyKDUPDGIRN~UHJXOiULV JUiI DNNRU YDQ RODQ WDUWRPiQD PHOHW OHJIHOMHEE  pO KDWiURO $] |WV]tQWpWHO EL]RQ WiViKR] UHQGUH PHJPXWDWMXN KRJ KDD*JUiIXQNQDNNHWW{KiURPQpJYDJ|WpOiOWDOKDWiUROW WDUWRPiQiW HOKDJMXN pV D] ~M *  JUiI |W V]tQQHO MyO V]tQH]KHW{ DNNRU * LV V]tQH]KHW{ OHJIHOMHEE |WV]tQQHO 6 PLYHO D *E{O V]iUPD]WDWRWW

JUiIRN WDUWRPiQDLQDN D V]iPD UHQGUH FV|NNHQQL IRJ HO{EE YDJ XWyEE HOMXWXQN HJ RODQ * Q JUiIKR] PHOQHN OHJIHOMHEE |W WDUWRPiQD YDQ V DNNRU D] PiU WULYLiOLVDQ V]tQH]KHW{ |WV]tQQHO 7HKiW D] |WV]tQWpWHO EL]RQ WiViKR] HOHJHQG{ PHJPXWDWQL KRJ KD D * JUiIQDN HOKDJMXN HJ N (2 ≤ k ≤ 5)  pOOHO KDWiUROW WDUWRPiQiW V D QHUW *  JUiI OHJIHOMHEE  V]tQQHO MyO V]tQH]KHW{ DNNRU  LV MyOV]tQH]KHW{V]tQQHO , 7HJNIHOD*KDUPDGIRN~UHJXOiULVVtNEDUDM]ROKDWy JUiIXQNQDNYDQHJ$WDUWRPiQDPHOHWD]DpVEFV~FVRNUD LOOHV]NHG{  pO KDWiURO /HJHQ D] D FV~FV PiVLN V]RPV]pGRV FV~FVD F pV E V]RPV]pGMD G 7|U|OMN D] D LOO E FV~FVRNDW pV D UiMXN LOOHV]NHG{ pOHNHW $ F LOO G FV~FVRNDW N|VVN |VV]H HJ ~M pOOHO +D D] $ D % pV & WDUWRPiQRNNDO % YROWKDWiURVPHOHNHWD],LOO,, , V]tQUH IHVWHWWQN pV $W ,,,UD DNNRU +D D] ~M *  JUiI % LOO & $

WDUWRPiQiQDN  D V]tQH]pVH , LOO ,,, & ,, DNNRU D] HUHGHWL iOODSRW KHOUHiOOtWiVD HVHWpQ  $ V]tQH ~MUD OHKHW ,,, V QHP NHOO YiOWR]WDWQL D * JUiIQDNHVHWOHJPHJOpY{W|EELWDUWRPiQiQDNDV]tQH]pVpQ F D E G ,,  ,,  +D D * JUiI D KiURPV]|JWDUWRPiQW WDUWDOPD]]D PHOHW D] $ % & WDUWRPiQRN $ KDWiUROQDN DNNRU D] DE FV~FVRNDW W|U|OYH HJHVtWVN D  pV D & % WDUWRPiQW V MHO|OMN PRQGMXN & YHO $] tJ QHUW *  JUiIQDN KD & D] $ ,YHO% ,,YHO pV & WDUWRPiQD ,,,YHO YDQ V]tQH]YH DNNRUD&WDUWRPiQWDYLVV]DiOOtWiVXWiQ,9YHOV]tQH]]N , ,, ,9 E D ,,, ,,,  7DUWDOPD]]D PRVW D * JUiIXQN D] ) WDUWRPiQW PHOHW QpJ ROGDO pV tJ QpJ WDUWRPiQ KDWiURO V MHO|OMH D]RNDW UHQGUH $%& $ QpJ WDUWRPiQ N|]O D V]HPEH IHNY{N N|]O IHOWpWOHQO YDQ NHWW{ P Q RODQ PHOHN QHP V]RPV]pGRVDN $] iEUiQNQDN PHJIHOHO{HQ OHJHQ % ,, D D] D NHWW{ PRVW % pV 

U (JHVtWVN D %) pV E S ,,, 9 WDUWRPiQRNDW RO PyGRQ KRJ D $ ) & ESXF SRQWRNDW pV D , F X UiMXN LOOHV]NHG{ pOHNHW G Y W|U|OMN 9DODPLQW D] DLOO G ,9 FV~FVRNDW pV D] U LOO Y FV~FVRNDW HJHJ ~M pOOHO N|WMN |VV]H $] LO PyGRQ QHUW *  JUiIQDN NHWW{YHO NHYHVHEE WDUWRPiQDYDQPLQW*QHNpVKDUPDGIRN~UHJXOiULVJUiI+D V]tQH]pVpEHQ $ LOO & V]tQH , LOO ,,, pV %) V]tQH ,, DNNRUDYLVV]DiOOtWiVXWiQ)V]tQHOHJHQ,9pVV]tQH,, ,9  /HJHQ PRVW * RODQ KRJ WDUWDOPD]]D D] $%&( ( H $ E D ) G F % & WDUWRPiQRN iOWDO KDWiUROW |WV]|JWDUWRPiQW +DVRQOy RNRVNRGiVVDO PLQW D] HO{EE EHOiWKDWy KRJ YDQ RODQ NpW WDUWRPiQ D] $%&( WDUWRPiQRN N|]|WW PHOHN QHP V]RPV]pGRVDN OHJHQHN D]RN SpOGiXO % pV  7|U|OMN *QHN EF W LOO HG W |VV]HN|W{ pOHLW ,WW HO{IRUGXOKDW KRJ D] $&( WDUWRPiQRN V]RPV]pGRVDN pV V]tQH]pVNK|] KiURP NO|QE|]{ V]tQ

NHOO PRQGMXN OHJHQHN D]RN UHQGUH ,,,,,, D QHJHGLN ,9 V]tQ )% V]tQH]pVpKH] NHOO 6 D] HUHGHWL JUiI YLVV]DiOOtWiViQiO D  pV % WDUWRPiQRN V]tQH OHKHW ,9 GH ) V]tQH]pVpKH] PiU IHO NHOO KDV]QiOQL D] 9 |W|GLN V]tQW ,O PyGRQEHEL]RQ WRWWXND]DOiEELWpWHOW 7pWHO  |WV]tQWpWHO  %iUPHO VtNED UDM]ROKDWy VRNV]|J JUiINLV]tQH]KHW{|WV]tQQHO  Ramsey-féle problémák HILQLFLy$]Q PN V]iPRW5DPVHIpOHV]iPQDNQHYH]]N KDUHQGHONH]LND]DOiEELWXODMGRQViJRNNDO L  KD D * (ϕ9  JUiIQDN D FV~FVSRQWMDLQDN D V]iPD V = n ≥ n(m, k )  DNNRU YDJ * QHN YDQ HJ P FV~FVSRQW~ WHOMHV UpV]JUiIMD YDJ * NRPSOHPHQWHUH WDUWDOPD] HJ N FV~FVSRQW~ WHOMHVJUiIRW LL YDQRODQ* ( ϕ 9 JUiIPHOQHNFV~FVSRQWMDLQDN DV]iPD V = n(m, k ) − 1 pV* QHNQLQFVPSRQW~WHOMHVUpV]JUiIMD pVDNRPSOHPHQWHUpQHNVLQFVNSRQW~WHOMHVUpV]JUiIMD $] LL  WXODMGRQViJJDO UHQGHONH]{ JUiIRNDW H[WUpP JUiIRNQDN QHYH]]N

6]HPOpOHWHVHEE PHJIRJDOPD]iVD D 5DPVH IpOH V]iPRNQDN D N|YHWNH]{ +D D] Q PN  SRQW~ WHOMHV JUiI pOHLW WHWV]pV V]HULQW SLURVUD YDJ ]|OGUH V]tQH]]N DNNRU vagy egy piros színû teljes m gráfot vagy egy zöld színû k WHOMHV JUiIRW NDSXQN WRYiEEi D] Q PN  SRQW~ WHOMHV JUiI pOHLW SLURV LOOHWYH ]|OG V]tQQHO OHKHW ~J V]tQH]QL KRJ VHP piros színû teljes m csúcspontú, sem zöld színû teljes k FV~FVSRQW~JUiIRWQHPWDUWDOPD] 57 7pWHO+D ∀P , N ∈ 1 DNNRU n(m, k ) = n(k , m)  %L]RQ WiV$V]tQHNIHOFVHUpOpVpYHODGyGLND]iOOtWiV 57 7pWHO+D ∀P , N ∈ 1 DNNRU n(1, k ) = n(m,1) = 1 n(2, k ) = k , n(m,2) = m  %L]RQ WiV $] HJ SRQWEyO iOOy JUiI QHP OpWH]{ pOpW HJDUiQW WHNLQWKHWMN SLURVQDN LOO ]|OGQHN LV +D D N SRQW~ WHOMHV JUiIQDN PLQGHQ V]tQH ]|OG DNNRU WDUWDOPD] HJ ]|OG színû teljes gráfot, ha csak egy éle is piros, akkor tartalmaz HJ  SRQW~ WHOMHV SLURV JUiIRW +D D] P SRQW~

WHOMHV JUiIQDN minden színe piros, akkor tartalmaz egy piros színû teljes JUiIRW KD FVDN HJ pOH LV ]|OG DNNRU WDUWDOPD] HJ  SRQW~ WHOMHV]|OGJUiIRW 57 7pWHO+DQ PN pV PN OpWH]LNDNNRUQ PN LVOpWH]LNpVQ PN ≤Q PN Q PN   %L]RQ WiV /HJHQ DGRWW D .Q PN Q PN  WHOMHV JUiI pV pOHLWHWV]{OHJHVHQV]tQH]YHSLURVVDOLOO]|OGGHOpVOHJHQX YDODPHOFV~FVSRQWMD-HO|OMHD*D]XEyOLQGXOySLURVpOHNpV * D] XEyO LQGXOy ]|OG pOHN YpJSRQWMDL iOWDO IHOIHV]tWHWW UpV]JUiIMDLW .Q PN Q PN QDN /HJHQ * FV~FVSRQWMDLQDN D V]iPDQpV*FV~FVSRQWMDLQDNDV]iPDQHNNRU Q1 + Q2 + 1 = Q(P -1,N )+ Q(P ,N -1) SLURV pOHN pV YDJ ,  Q1 ≥ Q(P -1,N ) YDJ ]|OG pOHN ,,  Q2 ≥ Q(P ,N -1) $] ,  HVHWEHQ * YDJ HJ P SRQW~ WHOMHV * * SLURVJUiIRWWDUWDOPD]pV*KH] KR]]iYpYH XW pV D] XEyO *EH X IXWy SLURV pOHNHW .Q PN Q PN  QHN HJ P SRQW~ WHOMHVHQ SLURVUpV]JUiIMiWNDSMXNKD*

EHQ N SRQW~ WHOMHV ]|OG UpV]JUiIXQN YROW DNNRU D] QLOYiQ UpV]JUiIMD .Q PN Q PN  QHNLVËJD] , HVHWEHQ.Q PN Q PN WDUWDOPD]YDJHJP SRQW~ WHOMHV SLURV YDJ HJ N SRQW~ WHOMHV ]|OG JUiIRW $ ,,  HVHWEHQ LV WHOMHVHQ KDVRQOyDQ EHOiWKDWy KRJ .Q P N Q PN WDUWDOPD]YDJHJPSRQW~WHOMHVSLURVYDJHJN SRQW~WHOMHV]|OGJUiIRWVH]]HODEL]RQ WiVNpV] 57 7pWHO (UG{V3iOpV6]HNHUHV*|UJ +D ∀P , N ∈ 1  m + k − 2 DNNRU n(m, k ) ≤    m−1  %L]RQ WiV N V]HULQWL WHOMHV LQGXNFLyYDO EL]RQ WXQN N  HVHWpQ WHWV]{OHJHV PUH Q P  5  V]HULQW pV PLYHO  m + 1 − 2 1≤    H]pUW HNNRU D] iOOtWiV LJD] 7pWHOH]]N IHO KRJ  m−1  D] iOOtWiVXQN WHWV]{OHJHV PUH LJD] N K HVHWpQ pV EL]RQ WVXN N KUD (] XWyEEL iOOtWiVW P V]HULQWL WHOMHV  1 + h − 2 LQGXNFLyYDO EL]RQ WMXN P  HVHWpQ 1 ≤    7HJN IHO  1− 1  KRJ P UH

PiU LJD] D] iOOtWiV  EL]RQ WVXN PUH (]HN V]HULQWWXGMXNKRJ  m + h − 3  m + h − 3 L  n(m − 1, h) ≤   pV n(m, h − 1) ≤    m−2   m −1  $] 57 V]HULQWHNNRUOpWH]LNQ PN pVNLVHEEHJHQO{ PLQWD]Q PN Q PN )HOKDV]QiOYDD] L EHFVOpVHNHW  m + k − 3  m + k − 3 (m + k − 3)! + (m + k − 3)! n(m, k ) ≤   + =  m − 2   m − 1  (k − 1)!(m − 2)! (k − 2)!(m − 1)!     m + k − 2 m−1 k −1  = = (m + k − 3)! +   (k − 1)!(m − 1)! (k − 1)!(m − 1)!  m − 1  PHJNDSMXNDWpWHOiOOtWiViW /HJHQHN U T T  T  HJQpO QDJREE YDJ HJJHO HJHQO{ HJpV] V]iPRN $] N (q1 , q2 ,., qt , r )  iOWDOiQRV  5DPVHV]iP KD HOHJHWWHV]DN|YHWNH]{IHOWpWHOHNQHN W  +D S ≥ N (q1 , q2 ,., qt , r )  DNNRU EiUPLOHQ Pr (S ) $ ∪ $ ∪∪ $ W HVHWpQ OpWH]LN RODQ i ∈{1,2,., t }  pV S , ⊆ S ,

hogy S , qi  pV KRJ Pr ( S , ) ⊆ Ai  D] N (q1 , q2 ,., qt , r ) QpO NLVHEE V]iP QHP UHQGHONH]LN D] HV WXODMGRQViJJDO  D]D] N (q1 , q2 ,., qt , r )  D OHJNLVHEE RODQ HJpV]DPHOUHD]WXODMGRQViJWHOMHVO 7pWHO$] N (q1 , q2 ,., qt ,1) q1 + q2 ++ qt − t + 1  0HJMHJ]pV Az elõbbiekben szereplô n(m,k) az N (m, k ,2) VSHFLiOLV HVHWQHN IHOHO PHJ $ Pr ( S ) az S halmaz r elemû UpV]KDOPD]DLQDNDKDOPD]iWMHO|OWH Generátorfüggvények, rekurzív sorozatok 7HUPpV]HWHV V]iPRN KDOPD]iQ JDNUDQ pUWHOPH]QHN RODQ valós esetleg komplex értékû f(n) függvényeket, melyeknek az n KHOHQ IHOYHWW pUWpNHL D]  Q  KHOHNHQ IHOYHWW pUWpNHLW{O IJJQHN 3pOGiXO HJ  pYH IHQQiOOy YiOODONR]iV DODSW{NpMH QLOYiQ IJJ D] HO{]{ pYHNEHQ D] DODSW{NH Q|YHOpVpUH HVHWOHJ FV|NNHQWpVpUH IRUGtWRWW |VV]HJHN QDJViJiWyO EiU H]HQ |VV]HIJJpVHN NLYiOWNpSS QDSMDLQNEDQ HOpJJp N|G|VHN OHKHWQHN 0L LWW FVXSiQ RODQ UHNXU]tY

|VV]HIJJpVHNNHO IRJXQN IRJODNR]QL PHOHW PDWHPDWLNiQ EHOO OLQHiULVDQUHNXU]tYVRUR]DWRNQDNV]RNiVQHYH]QL HILQtFLy$] 5.,  un + k = a k −1 u n + ( k −1) + a k − 2 u n + ( k − 2 ) ++ a 1 u n +1 + a 0 u n  D]DLNYDOyVYDJNRPSOH[NRQVWDQVRN NpSOHWWHOpVD] X0 ,X1 ,X2 ,.,XN − 2 ,XN −1 NH]G{ pUWpNHNNHO DGRWW VRUR]DWRW k-ad rendû OLQHiULVDQUHNXU]tYVRUR]DWQDNQHYH]]N Másodrendû lineáris rekurzív sorozatok körébôl máig a legnépszerûbb, s valószínûleg a legrégibb példa a FibonacciVRUR]DW X0 = 0, X1 = 1, X2 = 1, X3 = 2 , X4 = 3, X5 = 8, ., XQ + 2 = XQ +1 + XQ  /HRQDUGR)LERQDFFL  HUHGHWL QHYH /HRQDUGR 3LVDQR SLVDL Leonardo)) Liber Abaki ( könyv az abakuszról ) c. mûvében MHOHQLN PHJ HO{V]|U $ )LERQDFFLVRUR]DW D N|YHWNH]{ SUREOpPiEyO NHOHWNH]HWW +iQ SiU Q~O V]iUPD]KDW HJHWOHQ SiUWyOKD L  PLQGHQ SiU KDYRQWD HJ SiUW QHP] DPHO D PiVRGLN KyQDSWyONH]GYHOHV]QHP]{NpSHVpV LL

PLQGHJLNQ~OKDOKDWDWODQ" HILQtFLy$] 5., k-ad rendû lineáris rekurzív sorozat NDUDNWHULV]WLNXVSROLQRPMiQDNQHYH]]NDN|YHWNH]{SROLQRPRW 5.  f ( x ) = x k − a k −1 x k −1 − a k − 2 x k − 2 −− a 2 x 2 − a 1 x − a 0  +D D] 5.  J|NHL α 1 , α 2 ,, α N  SiURQNpQW NO|QE|]{HN DNNRU DVRUR]DWQWDJMDIHOtUKDWy 5.  u n = c k α nk + c k −1α nk −1 ++ c2 α n2 + c1α 1n DODNEDQ +D D]RQEDQ FVDN PQ  J|NQN YDQ V D] L J|N PXOWLSOLFLWiVDVLDNNRUVRUR]DWXQNQWDJMDD]DOiEELDODNEDQ tUKDWy 5.  X = Q L =P ∑α L Q L F + F α + + F L  L  = L L VL α − VL L − +F α L VL VL L −  /iWKDWyKRJDVRUR]DWiOWDOiQRVDODNMDWHOMHVHQDQDOyJ D] iOODQGy HJWWKDWyM~ OLQHiULV GLIIHUHQFLiO HJHQOHWHN PHJROGiViYDO 7pWHO +D D] un + k = a k −1 u n + ( k −1) + a k − 2 u n + ( k − 2 ) +.+ a 1 u n +1 + a 0 u n |VV]HIJJpVW D =1 (]1,1 ,]1,2 ,.,]1,M ,) =2 (]2,1 ,]2,2 ,,]2,M ,)

=N (]N ,1 ,]N ,2 ,,]N ,M ,) VRUR]DWRN NLHOpJtWLN DNNRU WHWV]{OHJHV F1 , F2 ,., FN  NRQVWDQVRN HVHWpQ NLHOpJtWL D 9 (Y 1 ,Y 2 ,.,Y M ,)  VRUR]DW LV DKRO v j = c1 z1, j + c2 z 2 , j +.+ c k z k , j  ( M = 0,1, 2 ,, Q ,)  %L]RQ WiV $ WpWHO IHOWpWHOHL V]HULQW EiUPHO L = 1, 2 ,., N pV (Q = N , N + 1, N + 2 ,., K,) HVHWpQWHOMHVOQHND]DOiEELD]RQRVViJRN  5.  z i ,n + k = a k −1 z i ,n + ( k −1) + a k − 2 z i ,n + ( k − 2 ) ++ a1 zi ,n +1 + a 0 z i ,n  6]RUR]]XN PHJ D] LW FLYHO PDMG DGMXN |VV]H {NHW  HNNRUIHOKDV]QiOYDD]WKRJY M = F1]1,M + F2]2 ,M +. +FN]N ,M DGyGLNKRJ  v n + k = a k −1 v n + ( k −1) + a k − 2 v n + ( k − 2 ) +.+ a1 v n +1 + a 0 v n V H] D] DPLW EL]RQ WDQL NHOOHWW 1HP RNR] NO|Q|VHEE QHKp]VpJHW PHJPXWDWQL KRJ KD D] 5.  UHNXU]tY |VV]HIJJpV NDUDNWHULV]WLNXV SROLQRPMiQDN αL J|NH DNNRU ]L,M = α LM ( M = 0,1, 2 ,., Q ,) VRUR]DWPHJROGiVD 5 QHN+DαLJ|NH 5 QHN 2 k

k −1 k −2  DNNRU α i = a k −1α i + a k − 2 α i +.+ a 2 α i + a1α i + a 0  D]RQRVViJRW YpJLJ V]RUR]KDWMXN α L QQHOpVOiWKDWyKRJD] 5. WHOMHVO 3pOGD$)LERQDFFLVRUR]DWNDUDNWHULV]WLNXVHJHQOHWH 1± 5 0LYHOXQWXQ = F1α 1Q + F2 α Q2 DODNEDQNHUHVVN 2 KHOpUH Q  pV Q W F1 , F2 UH NDSMXN D] DOiEEL [ 2 = [ + 1, J|NHL α 1,2 = tUMXQN EH Q OLQHiULVHJHQOHWUHQGV]HUW F + F = 1 PHOQHNPHJROGiVD F1 = −F2 = $ )LERQDFFL  5 F − F =  VRUR]DWQHOHPpWH]HNV]HULQWtUKDWMXND] n 1 1+ 5 1 1− 5   −   5.  un = 5 2  5 2  n alakban, mely távolról sem tûnik triviálisnak. 0HJHPOtWMN KRJ NO|Q IROyLUDWD YDQ D )LERQDFFLIpOH V]iPRNQDN 5HNXU]tY VRUR]DWRNUD YRQDWNR]yODJ QHP]HWN|]LOHJ LV HOLVPHUW V]pS HUHGPpQHN NDSFVROyGQDN .LVV 3pWHU pV 3HWK{ $WLOODQHYpKH]PLQGNHWWHQD *{U.iOPiQiOWDOOpWUHKR]RWW GHEUHFHQLV]iPHOPpOHWLLVNRODMHOHVV]HPpOLVpJHL

$JHQHUiWRUIJJYpQHOQHYH]pVWW|EEIpOHpUWHOHPEHQ LV KDV]QiOMiN D PDWHPDWLND NO|QE|]{ WHUOHWHLQ 0L LWW NpWIpOH OHKHWVpJHV pUWHOPH]pVW IRJXQN PHJHPOtWHQL (O{V]|U D] ~J QHYH]HWW SDUWtFLyV SUREOpPiNUD YRQDWNR]y JHQHUiWRU IJJYpQHNU{O EHV]pOQN /HJHQHN DGRWWDN D] Q1 , Q2 ,., QN  SR]LWtY HJpV]HN .pUGH]]N KRJ D] P V]iP KiQIpOHNpSSHQ iOOtWKDWy HO{ D] Q1 , Q2 ,., QN N |VV]HJHLNpQW RO PyGRQ KRJ EiUPHO Q1 , Q2 ,., QN  V]iPRW W|EEV]|U LV IHOKDV]QiOKDWXQN pV D VRUUHQG QHP V]iPtW $ SDUWtFLyV SUREOpPiQDN D] HO{EEL YiOWR]DWiW V]RNiV SpQ]YiOWiVL SUREOpPiQDN LV QHYH]QL 9L]VJiOMXN PHJ SpOGiXO KRJ YDODPHO V]iPRW KiQIpOHNpSSHQ OHKHW HO{iOOtWDQL D]  V]iPRN |VV]HJHNpQW 7HNLQWVN D N|YHWNH]{IJJYpQW  ( )( ) f ( x ) = 1 + x 1 + x 2 +.+ x n + ⋅ 1 + x 2 + x 4 ++ x 2 n + ( )( ) *.  ⋅ 1 + x 3 + x 6 ++ x 3n + ⋅ 1 + x 5 + x 10 ++ x 5n + = = (1 − x )(1 − x 1 2 )(1 − x )(1 − x ) 3

5 $] I [  IJJYpQ OHV] H] HVHWEHQ D JHQHUiWRU IJJYpQ 1HP YL]VJiOMXN KRJ D] I [  HO{iOOtWiViEDQ V]HUHSO{ KDWYiQVRURN NRQYHUJHQVHN H YDJ VHP +D D] I [ W KDWYiQVRUEDIHMWMN *.  f ( x ) = 1 (1 − x )(1 − x )(1 − x )(1 − x ) 2 3 5 = A0 + A1 x + A2 x 2 +.+ Am x m + DNNRU D] $P HJWWKDWy IRJMD PHJPXWDWQL KRJ PW KiQIpOHNpSSHQ OHKHW IHOtUQL D]  V]iPRN |VV]HJHLNpQW $]  $P HJWWKDWyN PHJKDWiUR]iViUD NO|QE|]{ PyGV]HUHN OpWH]QHN (J OHKHW D N|YHWNH]{ $ *.  QHYH]{MpEHQ D V]RU]iVRNDWHOYpJH]YHDGyGLN *.  f ( x ) = (1 − x − x 1 2 +x +x −x −x 4 7 9 10 +x 11 ) = A0 + A1 x + A2 x 2 +.+ Am x m +  $ QHYH]{YHO YpJLJ V]RUR]YD V ILJHOHPEH YpYH KRJ [P HJWWKDWyMD  D EDOROGDORQ KD P! D] $P HJWWKDWyNUD D] DOiEELUHNXU]tY|VV]HIJJpVWQHUMN *. $ P = $ P −1 + $ P −2 − $ P −4 − $ P − 7 + $ P −9 + $ P −10 − $ P −11 $ 

$NH]GHWLpUWpNHNUHKDPDNNRU$P pVKDP DNNRU 0iV PyGRQ LV PHJKDWiUR]KDWMXN D *.  IRUPXOD MREE ROGDOiQ iOOy KDWYiQVRU HJWWKDWyLW $ *.  IRUPXOD MREE ROGDOiQYpJH]]NHOD]RV]WiVW *.  f ( x ) = (1 − x − x 1 2 + x 4 + x 7 − x 9 − x 10 + x 11 ( ) ) 1 : 1 − x − x 2 + x 4 + x 7 − x 9 − x 10 + x 11 = 1 + x + 2 x 2 + 3x 3 + 4 x 4 + 6 x 5 +. x + x 2 − x 4 − x 7 + x 9 + x 10 − x 11 2 x 2 + x 3 − x 4 − x 5 − x 7 − x 8 + x 9 + 2 x 10 − x 12 3x 3 + x 4 − x 5 − 2 x 6 − x 7 − x 8 − x 9 + 2 x 10 + 2 x 11 + x 12 − 2 x 13 4 x 4 + 2 x 5 − 2 x 6 − 4 x 7 − x 8 − x 9 − x 10 + 2 x 11 + 4 x 12 + x 13 − 3x 14 6 x 5 + 2 x 6 − 4 x 7 − 5x 8 − x 9 − x 10 − 2 x 11 + 4 x 12 + 5x 13 + x 14 − 4 x 15  $]DOiEELGHILQtFLyEDQHJVRUR]DWKR]PiVPyGRQUHQGHOQN JHQHUiWRUIJJYpQW HILQtFLy $GRWW $ D0 , D1 ,., DQ ,  VRUR]DW 2 m JHQHUiWRUIJJYpQHD] f ( x ) = a 0 + a1 x + a 2 x +.+ a m x

+KDWYiQVRU $] HVHWHN W~OQRPy W|EEVpJpEHQ LWW VHP pUGHNHV KRJ D GHILQtFLyEDQ V]HUHSO{ KDWYiQVRU PLOHQ LQWHUYDOOXPRQ NRQYHUJHQV eUGHPHVPHJYL]VJiOQLDJHQHUiWRUIJJYpQHNVHJtWVpJpYHOD )LERQDFFLVRUR]DWRW/HJHQ *.  G( x ) = u0 + u1 x + u2 x 2 ++ un x n + D)LERQDFFLVRUR]DWJHQHUiWRUIJJYpQHD]HO{]{GHILQtFLy pUWHOPpEHQ V V]RUR]]XN PHJ [[HO PDMG [WHO QHUMN D] DOiEELNpSOHWHNHW *.  xG( x ) = u0 x + u1 x 2 + u2 x 3 ++ un x n +1 + *.  x 2 G( x ) = u0 x 2 + u1 x 3 + u2 x 4 ++ un x n + 2 +  KRJ +DD *. E{OUHQGUHOHYRQMXN *. WpV *. WDGyGLN ( ) *.  1 − x − x 2 G( x ) = u0 + (u1 − u0 ) x + (u2 − u1 − u0 ) x 2 ++ (un − un −1 − un − 2 ) x n + [ A (GK8)-ból PHJNDSKDWy *.  G( x ) = G(x) zárt alakja egyszerû osztással x  1− x − x2 $* [ MREEROGDOiQiOOyUDFLRQiOLVW|UWIJJYpQWERQWVXN SDUFLiOLV W|UWHN |VV]HJpUH D YDOyV WHVW IHOHWW )LJHOHPEH 1 YpYHKRJDQHYH]{EHQV]HUHSO{SROLQRPJ|NHL

−1 ± 5  2 ( *.  G( x ) = ) 1  1 1  x = +   2 1− x − x 5  1 − αx 1 − α x  DKRO α = 1 − α = ( ) 1 1 − 5  $ 2 *.  MREE ROGDOiQ V]HUHSO{ 1 1 , 1 + α [ + α 2[ 2 +. + αQ[ Q +  IJJYpQHN D] 1 − α[ 1 − α[ 1 + α [ + α 2[ 2 +. + α Q[ Q + PpUWDQL VRURNNDO HJH]QHN PHJ )LJHOHPEH YpYH KRJ DEV]RO~W NRQYHUJHQVHN DONDOPDV PyGRQ iWUHQGH]YH PHJNDSMXN KRJ D )LERQDFFLVRUR]DW WDJMDL tUKDWyN  n 1  n  α − α  DODNEDQ|VV]KDQJEDQDNRUiEELHUHGPpQQHO 5.   5 WDO 0HJMHJH]]N KRJ D )LERQDFFLVRUR]DWQDN H]W D] DODNMiW D IHQWL OHYH]HWpVL WHFKQLND KDV]QiODWiYDO / GH 0RLYUH PiU EDQN|]|OWH un =