ࡱ> I( F/ 0|DTimes New RomanC0Wo 0DVerdanaw RomanC0Wo 0" DBatangw RomanC0Wo 00DSymbolw RomanC0Wo 0@DComic Sans MSnC0Wo 0B ` . @n?" dd@  @@`` $4 h   &; (   B D5c $ ff3333f@7uʚ;2Nʚ;g4ZdZd0Pppp@ <4!d!d 0LlD<4dddd 0LlD ? %'! !"#%& $P  ` ` ̙33` 333MMM` ff3333f` f` f` 3` 3f333MMM>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>>  0  F(    6~ P  PKliknij, aby edytowa styl wzorca tytuBu) )  0d   Kliknij, aby edytowa style wzorca tekstu Drugi poziom Trzeci poziom Czwarty poziom Pity poziom*   a  0` ``  T*   0܋ `   V*   0 `   V* H  0޽h ? .\333MMM  Projekt domy[lny  c[0(  =  <$p,$D 0 5Directed paths decomposition of complete multidigraph660, & v  <$4 n ,$D 0 lZdzisBaw SkupieD Mariusz Meszka AGH UST Krakw, Poland770 H  0޽h ? ̙331   @':l I(  l l S @/4`@<$D 0  4 DPFor a given graph G of order n, the symbol G stands for a -multigraph on n vertices, obtained by replacing each edge of G by  edges (with the same endvertices).          .    %               ;l   1l ,$D 0`B l 0D){ N`B l 0D)R %`B l 0D){ %`B l 0D)%%2 l  `f3vd @f3 2  l  `f3vd @f3 2  l  `f3vd @f3  2  l  `f3vd @f3    l 6C40 QG  z   5l  ,$D  0 l 64G4`0D R4G   T P l#  ]  l  B C DEF> $X @   Pp@ l  B C DEF> p8 @   Pp@ l  B C DEF> 08`0pp  @   p@ l  B C DEF> dX`  @   p@ l  B C`DEF>`0x@0 `@   p@ l  B C DEF> x@ @   p@  l  B CDEF>Hp8H @   @p !l  B CDEF>xp( 0@   @pN @ "l @ #l  BC DEF>HxH @  p@ $l  BC DEF> H8pH@  p@ %l  BC DEF>@@ @  p@ &l  BXC DEF>HHPXx0 @  p@N @ 'l  @ (l  BC DEF>HxH @  p@ )l  BC DEF> H8pH@  p@ *l  BC DEF>@@ @  p@ +l  BXC DEF>HHPXx0 @  p@2 ,l  `f3vd @f3  2 -l  `f3vd @f3 2 .l  `f3vd @f3  2 /l  `f3vd @f3  9l 6Q43@ ` ,$D 0 <  ` :l s *LW4 l,$D 0  If G @ Kn then the symbol Kn denotes the complete -multigraph on n vertices. S                          H l 0޽h ? .\333MMM"  PtJ(  t t S 8l4 <$D 0  4 r A decomposition of a multigraph G is a family of edge-disjoint submultigraphs of G which include all edges of G.~s    1     l   H  H t 0޽h ? .\333MMM  VN`(    S {4P`<$D 0  4 XLTheorem [M. Tarsi; 1983] Necessary and sufficient conditions for the existence of a decomposition of Kn into paths of length m are n(n-1) 0 (mod 2m) and n m+1.3M    #      `  s *<4@ 0 ,$D 0 <[C. Huang] [S. Hung, N. Mendelsohn; 1977] handcuffed designs*=*H T  <40 ,$D 0 6[P. Hell, A. Rosa; 1972] resolvable handcuffed designs*70 H  0޽h ? .\333MMM  |p(  D  S  <$D 0  4 Theorem [M. Tarsi; 1983] The complete multigraph Kn is decomposable into undirected paths of any lengths provided that the lengths sum up to n(n-1)/2, each length is at most n-3 and, moreover, n is odd or  is even.3 Z       C         <4  ,$D 0 [K. Ng; 1985] improvement on any nonhamiltonian paths in the case n is odd and =1nU 7           H  0޽h ? .\333MMMX  ^XVX0 W(  B  6X4O,$D 0 n=9 =1N    (  ,z jt  &  tx ,$D 0N Uo  ' -ZB ( s *D>W  ZB ) s *D>g o o ZB * s *D>d }ZB +B s *D>\vwZB ,B s *D>U  ZB - s *D>\ e ZB . s *D>d  e  /  Bp CDEF>K B p @  \v~  N jt  0 jt 2 1 Zf3vd @f36 2 2 Zf3vd @f3 l 2 3 Zf3vd @f3` ;0 2 4 Zf3vd @f3nV%2 5 Zf3vd @f3bU2 6 Zf3vd @f3mU$2 7 Zf3vd @f3 Q 2 8 Zf3vd @f3q @ V 2 9 Zf3vd @f3wg. : <H4_ /  S0  ; <4  S1  < <@4C^* S2  = <4UX< S3  > 04 i  S4  ? <4q A t  S5  @ <4Xj? S6  A <T4OZ6 S7  B <\4   b( &z jt  C  tx ,$D 0N Nl  D - ZB EB s *D3f>b< }ZB F s *D3f>b }ZB GB s *D3f>N ~ ZB HB s *D3f>W l ZB I s *D3f> _ ZB JB s *D3f> ~ l ZB K s *D3f>C  e  L  BA CDEF3f>CSa *A @  \v~  N jt  M jt 2 N Zf3vd @f36 2 O Zf3vd @f3 l 2 P Zf3vd @f3` ;0 2 Q Zf3vd @f3nV%2 R Zf3vd @f3bU2 S Zf3vd @f3mU$2 T Zf3vd @f3 Q 2 U Zf3vd @f3q @ V 2 V Zf3vd @f3wg. W <T_ /  S0  X <T  S1  Y < TC^* S2  Z < TUX< S3  [ 0T i  S4  \ <Tq A t  S5  ] <8TXj? S6  ^ <TOZ6 S7  _ <T   b( &z jt  `  tx ,$D 0N   a  ZB b s *D3>ZB c s *D3>6 ZB d s *D3>6 6 ZB e s *D3>   ZB f s *D3> ZB g s *D3>ZB h s *D3> i  BCoDEF3>oH|'?@  C   N jt  j jt 2 k Zf3vd @f36 2 l Zf3vd @f3 l 2 m Zf3vd @f3` ;0 2 n Zf3vd @f3nV%2 o Zf3vd @f3bU2 p Zf3vd @f3mU$2 q Zf3vd @f3 Q 2 r Zf3vd @f3q @ V 2 s Zf3vd @f3wg. t <&T_ /  S0  u <*T  S1  v <(TC^* S2  w <2TUX< S3  x 0$,T i  S4  y <8Tq A t  S5  z <C ZB  s *D>C ZB  s *D> ZB  s *D>/  ZB  s *D> ZB  s *D> ZB B s *D>   BCgDEF>g&Qm(6@  (   N jt   jt 2  Zf3vd @f36 2  Zf3vd @f3 l 2  Zf3vd @f3` ;0 2  Zf3vd @f3nV%2  Zf3vd @f3bU2  Zf3vd @f3mU$2  Zf3vd @f3 Q 2  Zf3vd @f3q @ V 2  Zf3vd @f3wg.  <MT_ /  S0   <,QT  S1   <TTC^* S2   <WTUX< S3   0@[T i  S4   <4Tq A t  S5   <4bTXj? S6   <xfTOZ6 S7   <iT   b(  z jt    tx ,$D 02  Zf3vd @f36 2  Zf3vd @f3 l 2  Zf3vd @f3` ;0 2  Zf3vd @f3nV%2  Zf3vd @f3bU2  Zf3vd @f3mU$2  Zf3vd @f3 Q 2  Zf3vd @f3q @ V 2  Zf3vd @f3wg.  <oT_ /  S0   <tT  S1   < wTC^* S2   <zTUX< S3   0xT i  S4   <8|Tq A t  S5   <hTXj? S6   <TOZ6 S7   <hT   b( >  <ȐT $] ,$D  0 & 0 1 7 2 6 3 5 4 @      <T $} ,$D  0 |& 1 2 0 3 7 4 6 5  3f   <@T0 $ ,$D  0 |& 2 3 1 4 0 5 7 6  3   6TP $,$D   0 |& 3 4 2 5 1 6 0 7   H  0޽h ? .\333MMM|   (  l  S ĥT0 <$D 0  T ^Conjecture [M. Tarsi; 1983] The complete multigraph Kn is decomposable into undirected paths of arbitrarily prescribed lengths provided that the lengths sum up to n(n-1)/2. 3 m      +        H  0޽h ? .\333MMM  #'| ,(  |O | c $T`<$D 0  T For a multigraph G, let DG denote a multidigraph obtained from G by replacing each edge with two opposite arcs connecting endvertices of the edge.d    '  U        /  Iz pp %| p,$D 0`B | 0D)ee `B | 0D) `B | 0D)e `B | 0D)e  2  |  `f3vd @f3 2  |  `f3vd @f3g p2  |  `f3vd @f3gppg 2  |  `f3vd @f3pg   | 6Tp QG   l  p &|p ,$D  0 | 6Tp dDG*    |  BC DEF> lPL @  ? {m fB | 6D) $  |  BCDEF>x(@  ? { fB |B 6D)   |  BCDEF>xl hx@  ^m fB | 6D) B  |  BCDEF>\T8H0@  {m fB | 6D)B ^  |  BCDEF>xl hx@   "m fB | 6D) B  |  BCDEF>\T8H0@  ?m fB | 6D)B ^  |  BpCDEF>x`p8p@  [B6  |  BCDEF>0@  ?^m fB | 6D)@  fB  |B 6D)$^ ] 2 !|  `f3vd @f3p^ 2 "|  `f3vd @f3  2 #|  `f3vd @f3  2 $|  `f3vd @f3 p^  '| s *3f ,$D 0H | 0޽h ? 3f333MMM  A((    c $ T00 <$D 0  T ^nFor a given graph G of order n, the symbol G stands for a -multigraph on n vertices, obtained by replacing each edge of G by  edges (with the same endvertices).          -    %                ' s *TT X0,$D 0 The symbol DKn denotes the complete -multidigraph on n vertices. D                      ( <T ,$D 0 w digraph D,  3 3 B . s *D3Ԕ` P,$D 00 / <T M,$D 0 -multidigraph, 3 $  d 2 s *V ,$D 0  on n vertices, obtained by replacing each edge of G by  edges (with the same endvertices)._  -    & t        B 6 s *D3ԔP@ P,$D 0 7 68 Vp ,$D  0  (with the same endvertices).. 3  B 8 s *D3Ԕ@P` @,$D  0B 9 s *D3Ԕ@0@,$D  00 = <V ,$D  0 arc of D,  3 38    > <V0 ,$D 0 Xarcs 3 D ? <,V M,$D  0 -multidigraph, 3 8    @ <@m,$D 0 xD0 3 3   B A s *D3Ԕz,$D 0H  0޽h ? .\333MMMZT  SSTvS(  Tz   T P,$D 0ZB T s *D){ NZB T s *D)R %ZB T s *D){ %ZB T s *D)%%2  T Zf3vd @f3 2  T Zf3vd @f3 2  T Zf3vd @f3  2  T Zf3vd @f3    T 0'V0 QG  z   T  -,$D  0 T 0*V`0D R4G   T P T#  ]  T  B C DEF> $X @   Pp@ T  B C DEF> p8 @   Pp@ T  B C DEF> 08`0pp  @   p@ T  B C DEF> dX`  @   p@ T  B C`DEF>`0x@0 `@   p@ T  B C DEF> x@ @   p@ T  B CDEF>Hp8H @   @p T  B CDEF>xp( 0@   @pN @ T @ T  BC DEF>HxH @  p@ T  BC DEF> H8pH@  p@ T  BC DEF>@@ @  p@ T  BXC DEF>HHPXx0 @  p@N @ T  @ T  BC DEF>HxH @  p@  T  BC DEF> H8pH@  p@ !T  BC DEF>@@ @  p@ "T  BXC DEF>HHPXx0 @  p@2 #T Zf3vd @f3  2 $T Zf3vd @f3 2 %T Zf3vd @f3  2 &T Zf3vd @f3 ~ z  p 1T  Pm,$D  0 2T 00Vp dDG*    3T  BC DEF> lPL @  ? {m `B 4T 0D) $  5T  BCDEF>x(@  ? { `B 6TB 0D)   7T  BCDEF>xl hx@  ^m `B 8T 0D) B  9T  BCDEF>\T8H0@  {m `B :T 0D)B ^  ;T  BCDEF>xl hx@   "m `B \T8H0@  ?m `B >T 0D)B ^  ?T  BpCDEF>x`p8p@  [B6  @T  BCDEF>0@  ?^m `B AT 0D)@  `B BTB 0D)$^ ] 2 CT Zf3vd @f3p^ 2 DT Zf3vd @f3  2 ET Zf3vd @f3  2 FT Zf3vd @f3 p^  GT s *3 ,$D 0 HT 0Z3f@ ,$D 0,l  0m T 0m,$D  0 cT 6:V  m s4DG8    T ys  dT# W (  eT  B C DEFo $X @  ys  fT  B C DEFo p8 @  ys  gT  B C DEFo 08`0pp  @  ys  hT  B C DEFo dX`  @  ys  iT  B C` DEFo` xpp` @   p  jT  B C DEFo (h4 @  Pp  kT  B C0 DEFo0 hX @  @ p  lT  B C` DEFo` xH p(  @  Pp  mT  BC DEFo H8pH@  p   nT  BC DEFoHxH @  ;   oT  BC DEFo@@ @     pT  BXC DEFoHHPXx0 @  m C  qT  BC0 DEFo0 hX@     rT  B C DEFo   @     sT  BC DEFo x00x@     tT  BC0 DEFo0 8(P@   r fB uT 6DԔ fB vT 6DԔ fB wT 6DԔ fB xT 6DԔ> > fB yT 6DԔ  fB zT 6DԔ  fB {TB 6DԔC C fB |T 6DԔr r 2 }T  `f3vd @f3   ~T  BC DEFo H8pH@  ? o T  BC DEFoHxH @   ? T  BC DEFo@@ @   ? T  BXC DEFoHHPXx0 @  +  T  BC0 DEFo0 hX@  > C T  B C DEFo   @   C T  BC DEFo x00x@  C  T  BC0 DEFo0 8(P@  C 0fB T 6DԔ> > fB T 6DԔ  fB T 6DԔ  fB T 6DԔ  fB T 6DԔr r fB T 6DԔ  fB T 6DԔ & fB T 6DԔ0 0 2 T  `f3vd @f3  fB T 6DԔw  fB T 6DԔ 1 fB T 6DԔ^  fB T 6DԔ4^ d fB TB 6DԔ  fB TB 6DԔ ) fB TB 6DԔ9 Q fB TB 6DԔQV il T ] y  T# z ( T  B C`DEFo`0x@0 `@   ys  T  B C DEFo x@ @  ] ys  T  B CDEFoHp8H @  s y  T  B CDEFoxp( 0@  s y  T  B CDEFop@ h @  M + T  B CDEFo`p8 @    T  B CDEFoxp0 ( @  q T  B CDEFop8 H @  +fB T 6DԔLM |M fB T 6DԔ|z z fB T 6DԔ4 d fB T 6DԔ|  fB TB 6DԔ44fB TB 6DԔ4q|qfB TB 6DԔfB TB 6DԔL|2 T  `f3vd @f3 2 T  `f3vd @f3  T s *3@ ` ,$D 0 T 0Z3f@ ,$D 0H T 0޽h ? 3f333MMM[       (  J  S (  <$D 0   rA decomposition of a multigraph G is a family of edge-disjoint submultigraphs of G which include all edges of G.s    2            .  R  0H@00,$D0u 0 "A decomposition of a multigraph G N#     *  >  <p M,$D 0 multidigraph D,  3 3@   B  s *D3ԔP P,$D 0F  6 @ ,$D 0  which include all edges of G.<   .  B  <0p ,$D 0 "arc-disjoint submultidigraphs of D,#! 3 30 B  s *D3Ԕ,$D 0B  s *D3Ԕ ` ,$D 0  << } ,$D  0 w arcs of D,  3 3 H  0޽h ? .\333MMM<     d (    S LXVp@<$D 0  V sProblem [E. Strauss; ~1960] Can the complete digraph on n vertices be decomposed into n directed hamiltonian paths?zt3p  c  0HcVFd,$D 0 %[J-C. Bermond, V. Faber; 1976] even n<&J   <$jV ,$D 0 D[T. Tillson; 1980] odd n, n 7 j#8     <8tVn w,$D 0 T2Theorem [J. Bosk; 1986] The multigraph DKn is decomposable into directed hamiltonian paths if and only if neither n=3 and  is odd nor n=5 and =1. 3J        #   H  0޽h ? .\333MMM  *(    S XV <$D 0  V `Problem [Z. SkupieD, M. Meszka; 1997] If the complete multidigraph DKn is decomposable into directed paths of arbitrarily prescribed lengths then the lengths must sum up to n(n-1), and moreover all paths cannot be hamiltonian if either n=3 and  is odd or n=5 and =1. Are the above necessary conditions also sufficient for the existence of a decomposition into given paths? 3  h; m4       0                 3 H  0޽h ? .\333MMM*     R (  j  S VP<$D 0  V Theorem [Z. SkupieD, M. Meszka; 1999] For n 3, the complete multidigraph DKn is decomposable into directed nonhamiltonian paths of arbitrarily prescribed lengths ( n-2) provided that the lengths sum up to n(n-1).3 W(     6        <VP,$D 0 VTheorem [Z. SkupieD, M. Meszka; 2004] For n 4, the complete multidigraph DKn is decomposable into directed paths of arbitrarily prescribed lengths except the length n-2, provided that the lengths sum up to n(n-1), unless all paths are hamiltonian and either n=3 and  is odd or n=5 and =1.,3[)-       #         $     H  0޽h ? .\333MMM  ~v(    S WP0 <$D 0  V DCorollary [Z. SkupieD, M. Meszka; 2004] Necessary and sufficient conditions for the existence of a decomposition of DKn into directed paths of the same length m are n(n-1) 0 (mod m) and m n-1, unless m=n-1 and either n=3 and  is odd or n=5 and =1. 3M )  h          )      &  H  0޽h ? .\333MMMD  l(  4  S "W <$D 0  W Conjecture [Z. SkupieD, M. Meszka; 2000] The complete multidigraph DKn is decomposable into directed paths of arbitrarily prescribed lengths provided that the lengths sum up to n(n-1), unless all paths are hamiltonian and either n=3 and  is odd or n=5 and =1.   3 l/ ^          /    ,    H  0޽h ? .\333MMMr`0Q %6[@AסO9w!p&D2<WDP I].HOh+'0 `h   Prezentacja programu PowerPointMariuszMariusz162Microsoft PowerPointPow@\@>@0bThGng  /'& &&#TNPP2OMi & TNPP &&TNPP    .\--- !---&G&w@ ؟ww wUf- &Gy& --YWhp-- @"Verdana  ؟ww wUf- .2 Directed paths1&!&((&)!. .2 decomposition of(&!'>('!'('. .'2 Fzcomplete multidigraph!'>(&&>)'(&((.--&-- Batang ؟ww wUf- .g@Batang L؟ww wUf-.2 gZdzisaw Skupie    .-. .2 oMariusz   . .2 Meszka. ."@Batang L؟ww wUf-.2 "AGH UST Krakw,    .-. .2 MPoland .--"SystemUf !-&TNPP &՜.+,0      0 Pokaz na ekranierWMS AGH^f Times New RomanVerdanaBatangSymbolComic Sans MSProjekt domyślny Prezentacja programu PowerPointFor a given graph G of order n, the symbol λG stands for a λ-multigraph on n vertices, obtained by replacing each edge of G by λ edges (with the same endvertices).s A decomposition of a multigraph G is a family of edge-disjoint submultigraphs of G which include all edges of G.Theorem [M. Tarsi; 1983] Necessary and sufficient conditions for the existence of a decomposition of λKn into paths of length m are λn(n-1)  0 (mod 2m) and n  m+1.Theorem [M. Tarsi; 1983] The complete multigraph λKn is decomposable into undirected paths of any lengths provided that the lengths sum up to λn(n-1)/2, each length is at most n-3 and, moreover, n is odd or λ is even. Prezentacja programu PowerPointConjecture [M. Tarsi; 1983] The complete multigraph λKn is decomposable into undirected paths of arbitrarily prescribed lengths provided that the lengths sum up to λn(n-1)/2.For a multigraph G, let DG denote a multidigraph obtained from G by replacing each edge with two opposite arcs connecting endvertices of the edge.For a given graph G of order n, the symbol λG stands for a λ-multigraph on n vertices, obtained by replacing each edge of G by λ edges (with the same endvertices). Prezentacja programu PowerPointsA decomposition of a multigraph G is a family of edge-disjoint submultigraphs of G which include all edges of G.tProblem [E. Strauss; ~1960] Can the complete digraph on n vertices be decomposed into n directed hamiltonian paths?Problem [Z. Skupień, M. Meszka; 1997] If the complete multidigraph λDKn is decomposable into directed paths of arbitrarily prescribed lengths then the lengths must sum up to λn(n-1), and moreover all paths cannot be hamiltonian if either n=3 and λ is odd or n=5 and λ=1. Are the above necessary conditions also sufficient for the existence of a decomposition into given paths?Theorem [Z. Skupień, M. Meszka; 1999] For n  3, the complete multidigraph λDKn is decomposable into directed nonhamiltonian paths of arbitrarily prescribed lengths ( n-2) provided that the lengths sum up to λn(n-1). Corollary [Z. Skupień, M. Meszka; 2004] Necessary and sufficient conditions for the existence of a decomposition of λDKn into directed paths of the same length m are λn(n-1)  0 (mod m) and m n-1, unless m=n-1 and either n=3 and λ is odd or n=5 and λ=1.Conjecture [Z. Skupień, M. Meszka; 2000] The complete multidigraph λDKn is decomposable into directed paths of arbitrarily prescribed lengths provided that the lengths sum up to λn(n-1), unless all paths are hamiltonian and either n=3 and λ is odd or n=5 and λ=1. Używane czcionkiSzablon projektuTytuły slajdów_f^0MariuszMariusz  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)Current UserSummaryInformation(PowerPoint Document(^DocumentSummaryInformation8