{"id":672,"date":"2010-01-06T09:16:10","date_gmt":"2010-01-06T08:16:10","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=672"},"modified":"2010-01-06T09:16:10","modified_gmt":"2010-01-06T08:16:10","slug":"wsrod-drzew","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2010\/01\/06\/wsrod-drzew\/","title":{"rendered":"W\u015br\u00f3d drzew"},"content":{"rendered":"

<\/a>Oto drzewo, nie wygl\u0105daj\u0105ce zbyt okazale.<\/p>\n

\"\"<\/a><\/p>\n

Przypomina resztki szkieletu choinki albo pewien gatunek kaktusa, kt\u00f3rego nazwy nie pami\u0119tam.
\nW teorii graf\u00f3w taki badyl, z\u0142o\u017cony z wierzcho\u0142k\u00f3w (punkty)\u00a0i \u0142\u0105cz\u0105cych je kraw\u0119dzi (odcinki)\u00a0nazywa si\u0119 w\u0142a\u015bnie drzewem. Aby jednak zas\u0142ugiwa\u0142 na to okre\u015blenie, ka\u017cde dwa wierzcho\u0142ki powinna \u0142\u0105czy\u0107 jedna i tylko jedna droga. Ponadto, by drzewo przypomina\u0142o drzewo, zwykle wyr\u00f3\u017cnia si\u0119 w nim jeden wierzcho\u0142ek, zwany korzeniem, a pozosta\u0142e rozmieszcza tak, aby wraz z \u0142\u0105cz\u0105cymi je kraw\u0119dziami tworzy\u0142y jakby\u00a0koron\u0119, cho\u0107\u00a0na og\u00f3\u0142\u00a0niezbyt bujn\u0105.<\/p>\n

Drzewo na rysunku ma 7 wierzcho\u0142k\u00f3w oraz\u00a0\u015brednic\u0119, kt\u00f3ra wynosi 4.\u00a0\u015arednica drzewa-grafu to najd\u0142u\u017csza\u00a0– z\u0142o\u017cona z najwi\u0119kszej liczby odcink\u00f3w\u00a0– droga mi\u0119dzy dwoma wierzcho\u0142kami; jednostk\u0105 d\u0142ugo\u015bci jest wi\u0119c\u00a0kraw\u0119d\u017a, czyli w tym przypadku kot wspinaj\u0105cy si\u0119 na drzewo „zaliczy” co najwy\u017cej 4 kraw\u0119dzie. Ze z\u0142a\u017ceniem na d\u00f3\u0142 koty miewaj\u0105 zwykle k\u0142opoty, wi\u0119c cofanie si\u0119 wykluczamy.
\nCzy istniej\u0105 inne drzewa o\u00a07 wierzcho\u0142kach i \u015brednicy r\u00f3wnej 4?
\nOwszem, jeszcze cztery. Oto one:<\/p>\n

\"\"<\/a><\/p>\n

W sumie zatem wszystkich drzew z 7 wierzcho\u0142kami i \u015brednic\u0105 r\u00f3wn\u0105 4 jest 5.
\nMam nadziej\u0119, \u017ce teraz b\u0119dzie zrozumia\u0142e stwierdzenie, dotycz\u0105ce osobliwego zwi\u0105zku liczby 2010 z teori\u0105 graf\u00f3w:
\nR\u00f3\u017cnych\u00a0 drzew z 15 wierzcho\u0142kami, kt\u00f3rych \u015brednica wynosi 7 jest dok\u0142adnie 2010<\/strong>.
\nPoni\u017csza \u0142amig\u0142\u00f3wka jest tak\u017ce „drzewna”, ale wi\u0105\u017ce si\u0119 z zupe\u0142nie innymi dzia\u0142ami dendrologii i matematyki.<\/p>\n

\"\"<\/a><\/p>\n

W ka\u017cdym polu nale\u017cy zasadzi\u0107 drzewo (D) lub krzew (K).
\nCyfra w polu z D powinna oznacza\u0107 liczb\u0119 s\u0105siaduj\u0105cych z tym polem kratek z K.
\nCyfra w polu z K powinna oznacza\u0107 liczb\u0119 s\u0105siaduj\u0105cych z tym polem kratek z D.
\nS\u0105siedztwo to stykanie si\u0119 bokiem lub rogiem.
\nDla\u00a0jasno\u015bci – ma\u0142y\u00a0przyk\u0142ad z lewej.<\/p>\n

Komentarze z prawid\u0142owymi<\/strong> rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co 3 dni.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Oto drzewo, nie wygl\u0105daj\u0105ce zbyt okazale. Przypomina resztki szkieletu choinki albo pewien gatunek kaktusa, kt\u00f3rego nazwy nie pami\u0119tam. W teorii graf\u00f3w taki badyl, z\u0142o\u017cony z wierzcho\u0142k\u00f3w (punkty)\u00a0i \u0142\u0105cz\u0105cych je kraw\u0119dzi (odcinki)\u00a0nazywa si\u0119 w\u0142a\u015bnie drzewem. Aby jednak zas\u0142ugiwa\u0142 na to okre\u015blenie, ka\u017cde dwa wierzcho\u0142ki powinna \u0142\u0105czy\u0107 jedna i tylko jedna droga. Ponadto, by drzewo przypomina\u0142o drzewo, […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/672"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=672"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/672\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=672"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=672"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=672"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}