i i “topologije-0” — 2009/10/15 — 13:53 — page 157 — #5 i i i i i i Splošna topologija in Topologija pleksnoceloto. Nekateretemesosetuprviˇ cpojavilevslovenskemuˇ cbeniku. Vaje so del glavnega besedila knjige in so namenjene nadgrajevanju podane snovi: bralec lahko kreativno sodeluje pri branju z lastnim dokazovanjem. Kot del glavnega besedila so bralcu na voljo ˇ stevilni premiˇ sljeni zahtevni zgledi, s katerimi lahko poglobi razumevanje snovi in gradi topoloˇ sko in geometriˇ cno intuicijo. Tempo podajanja snovi in ˇ sirina snovi sta primerna tudi za najzahtevnejˇ se bralce. Jaka Smrekar Wilfried Imrich, Sandi Klavˇ zar in Douglas F. Rall: TOPICS IN GRAPH THEORY: GRAPHS AND THEIR CARTESIAN PRO- DUCT, A K Peters, Wellesley, Massachusetts, 2008, 220 strani. V svetovnem matematiˇ cnem letu 2000 je pri zaloˇ zbi Wiley-Interscience izˇ sla knjiga WilfriedaImrichainSandijaKlavˇ zarjazna- slovomProduct Graphs: Structure and Reco- gnition,kijeprviˇ cnaenemmestuzbralavse glavne rezultate o strukturi in algoritmiˇ c- nihlastnostihnajpomembnejˇ sihˇ stirihgrafo- vskih produktov: karteziˇ cnega, direktnega, krepkega in leksikografskega. Knjiga je pri raziskovalcih, pedagogih in ˇ studentih doˇ zi- vela zelo lep sprejem. Zdaj je pred nami nova knjiga istih av- torjev, ki se jima je pridruˇ zil ˇ se Douglas F. Rall, izdala pa jo je zaloˇ zba A K Peters. Skupaj s knjigo Graphs on Surfaces Bojana Moharja in Carstena Thomassena, ki jo je leta 2001 izdala zaloˇ zba Johns Hopkins University Press, je to ˇ ze tretja knjiga slovenskih (so)avtorjev na podroˇ cju teorije grafov, objavljena pri ugledni mednarodni znanstveni za- loˇ zbi. Ta podatek prav gotovo potrjuje vitalnost in prodornost slovenske diskretne matematike in ˇ se posebej teorije grafov v svetovnem merilu. Predenseposvetimovsebininoveknjige,povejmonekajbesedoavtorjih. Wilfried Imrich je profesor na Montanistiˇ cni univerzi v Leobnu (Avstrija). SandiKlavˇ zarjeprofesornauniverzahvLjubljaniinMariboru. Vletu2000 je prejel Zoisovo priznanje za pomembne znanstvene doseˇ zke v matematiki na podroˇ cju teorije grafov, v letu 2007 pa Zoisovo nagrado za vrhunske znanstvene in razvojne doseˇ zke na podroˇ cju matematike. Douglas F. Rall Obzornik mat. fiz. 56 (2009) 4 157 i i “topologije-0” — 2009/10/15 — 13:53 — page 158 — #6 i i i i i i Nove knjige je profesor na Furmanovi univerzi v Greenvilleu (Juˇ zna Karolina, ZDA). Ker so avtorji sami vodilni raziskovalci na podroˇ cju grafovskih produktov, prinaˇ sa knjiga veliko sveˇ zih rezultatov, ki so bili objavljeni v znanstvenih revijah pribliˇ zno soˇ casno z izidom knjige. Hkrati je bila knjiga ˇ ze pred izidom temeljito preskuˇ sena pri podiplomskih teˇ cajih na domaˇ cih univerzah avtorjev. Zasnova knjige je zanimiva in inovativna: za rdeˇ co nit so avtorji izbrali karteziˇ cne produkte grafov in njihove podgrafe, ki imajo zaradi svojih le- pih metriˇ cnih lastnosti ˇ stevilne uporabe v teoriji kodiranja, dodeljevanju radijskih frekvenc, teoretiˇ cni kemiji in drugod. Ob tej vodilni t´ emi bralec spozna vsa pomembna podroˇ cja teorije grafov – od povezanosti, hamilton- skosti in ravninskosti prek ˇ stevilnih invariant do metriˇ cnih, algebraiˇ cnih in algoritmiˇ cnih vidikov. Knjiga je tako razdeljena na pet delov, vsak od njih pa obsega veˇ c poglavij, ki jih je v celoti osemnajst. Zelo pohvalno je, da poglavja v povpreˇ cju ne presegajo deset strani, kar naredi knjigo berljivo in dostopno tudi manj veˇ sˇ cim bralcem. Dobrodoˇ sli so tudi kratki ” napove- dniki“ na zaˇ cetku vsakega poglavja, ki podajajo pregled vsebine poglavja in ga umeˇ sˇ cajo v ˇ sirˇ si kontekst. V prvem delu knjige spoznamo definicijo in osnovne lastnosti karteziˇ c- nega produkta grafov ter nekaj praktiˇ cno pomembnih druˇ zin grafov, ki so definirane ali karakterizirane z njegovo pomoˇ cjo. To so hiperkocke (kar- teziˇ cne potence polnega grafa K 2 ), Hammingovi grafi (karteziˇ cni produkti poljubnihpolnihgrafov)inhanojski grafi (vpetipodgrafiHammingovihgra- fov, ki ustrezajo prostoru stanj pri reˇ sevanju znanega problema hanojskega stolpa). V drugem delu se sreˇ camo s hamiltonskostjo, ravninskostjo, prekri- ˇ znimiˇ stevili, povezanostjo in podgrafi, najprej v sploˇ snem, nato paˇ se s po- sebnim ozirom na karteziˇ cne produkte grafov. Navedena je odprta domneva Rosenfelda in Barnetta iz leta 1973, da je prizma (karteziˇ cni produkt z gra- fom K 2 ) nad poljubnim 3-povezanim ravninskim grafom hamiltonski graf, hkrati pa je podan eleganten dokaz izreka, da jek-kratna prizma (karteziˇ cni produktzgrafomK k 2 )nadtakimgrafomhamiltonskigrafzavsek≥2. Do- kaz med drugim uporablja tudi karakterizacijo hamiltonskosti karteziˇ cnega produkta hamiltonskega grafa in drevesa avtorjev Batagelja in Pisanskega iz leta 1982. Tretji del knjige je posveˇ cen grafovskim invariantam, kot so neodvisnostno ˇ stevilo, kromatiˇ cno ˇ stevilo, P-kromatiˇ cno ˇ stevilo (kjer je P neka dedna lastnost grafov), kroˇ zno kromatiˇ cno ˇ stevilo, seznamsko kroma- tiˇ cnoˇ stevilo,L(2,1)-oznaˇ cevalnoˇ stevilo, kromatiˇ cni indeks in dominacijsko ˇ stevilo. Avtorjisizastavijozanimivovpraˇ sanje, kajlahkopovemoovredno- stinekeinvariantenakarteziˇ cnemproduktu,ˇ cepoznamonjenevrednostina 158 Obzornik mat. fiz. 56 (2009) 4 i i “topologije-0” — 2009/10/15 — 13:53 — page 159 — #7 i i i i i i Topics in Graph Theory posameznih faktorjih. Kot izvemo, so razmere pri razliˇ cnih invariantah zelo razliˇ cne: medtem ko je npr. razmeroma preprosto videti, da je kromatiˇ cno ˇ stevilo karteziˇ cnega produkta enako najveˇ cjemu izmed kromatiˇ cnih ˇ stevil njegovih faktorjev, pa je Vizingova domneva iz leta 1968, ki pravi, da je do- minacijskoˇ stevilokarteziˇ cnegaproduktaveˇ cjealikveˇ cjemuenakoproduktu dominacijskih ˇ stevil faktorjev, ˇ se vedno odprta. Kotˇ ze omenjeno, velika praktiˇ cna uporabnost karteziˇ cnih produktov iz- haja predvsem iz njihovih lepih metriˇ cnih lastnosti, s katerimi se ukvarja ˇ cetrti del knjige. Avtorji npr. pokaˇ zejo, da sta premer oziroma polmer kar- teziˇ cnega produkta grafov enaka vsoti premerov oziroma polmerov njegovih faktorjev in da je mogoˇ ce njegov Wienerjev indeks (s katerim v teoretiˇ cni kemiji opisujejo fizikalno-kemiˇ cne lastnosti molekul) preprosto izraˇ cunati iz vrednostiWienerjevegaindeksafaktorjev. Medpodgrafikarteziˇ cnihproduk- tov avtorji posebej izpostavijo izometriˇ cne podgrafe, pri katerih se metrika podgrafa ujema z zoˇ zitvijo metrike celotnega grafa na mnoˇ zico vozliˇ sˇ c pod- grafa. Tako npr. izometriˇ cne podgrafe hiperkock imenujemo delne kocke, izometriˇ cne podgrafe Hammingovih grafov pa delni Hammingovi grafi. Ta del knjige se sklene z dokazom fundamentalnega izreka metriˇ cne teorije kar- teziˇ cnih produktov, ki pravi, da ima vsak graf k´ anonsko metriˇ cno predsta- vitev, tj. enoliˇ cno izometriˇ cno vloˇ zitev v karteziˇ cni produkt z maksimalnim ˇ stevilom neredundantnih faktorjev. Peti del knjige obravnava algebraiˇ cne in algoritmiˇ cne lastnosti karte- ziˇ cnih produktov. ˇ Ce izomorfnih grafov ne loˇ cimo med seboj, je mnoˇ zica grafov, opremljena s karteziˇ cnim produktom, Abelov monoid z enoto K 1 . Po analogiji s praˇ stevili imenujemo grafe, ki nimajo netrivialnih karteziˇ cnih razcepov, pragrafi. Avtorji pokaˇ zejo, da izrek o enoliˇ cnem razcepu grafa na pragrafe velja za vse povezane grafe, za nepovezane pa v sploˇ snem ne. Zato je kar presenetljivo, da za vse grafe (tudi nepovezane) veljata pravili krajˇ sanja in enoliˇ cnosti r-tih korenov. S pomoˇ cjo enoliˇ cnega razcepa pove- zanega grafa na pragrafe avtorji razkrijejo strukturo grupe avtomorfizmov povezanega grafa: le-ta je izomorfna grupi avtomorfizmov disjunktne unije prafaktorjev grafa. Te rezultate uporabijo za analizo razlikovalnega ˇ stevila grafa, tj. najmanjˇ sega naravnega ˇ stevila d, za katero obstaja oznaˇ citev vo- zliˇ sˇ c grafa z d oznakami, ki jo ohranja le identiˇ cni avtomorfizem. Tako npr. dokaˇ zejo, da je razlikovalnoˇ stevilo k-te karteziˇ cne potence poljubnega netrivialnega povezanega grafa, razliˇ cnega od grafov K 2 in K 3 , enako 2 za vse k≥ 2. Nazadnje avtorji predstavijo dva pomembna algoritma, in sicer za razcep povezanega grafa na pragrafe in za razpoznavanje delnih kock, oba s ˇ casovno zahtevnostjo O(mn), kjer je n ˇ stevilo vozliˇ sˇ c, m pa ˇ stevilo Obzornik mat. fiz. 56 (2009) 4 159 i i “topologije-0” — 2009/10/15 — 13:53 — page 160 — #8 i i i i i i Nove knjige povezav danega grafa. Posebnadragocenostknjigesonaloge,skaterimisekonˇ cavsakopoglavje in ki jih je skupaj veˇ c kot dvesto. Na koncu knjige najdemo reˇ sitev ali vsaj namigzareˇ sitevpravvsakeodnalog. Seznamliteratureobsega122referenc, sledijo pa mu tri koristna kazala: imensko kazalo, kazalo oznak in stvarno kazalo. Knjiga bo rabila raziskovalcem na podroˇ cju grafovskih produktov kot enciklopedija znanih rezultatov, pedagogom in ˇ studentom kot izvrsten uˇ c- benik, veseli pa je bodo tudi vsi drugi ljubitelji teorije grafov, ki se ˇ zelijo seznaniti z najnovejˇ simi rezultati na tem podroˇ cju. Marko Petkovˇ sek William P. Berlinghoff in Fernando Q. Gouvˆ ea: MATEMATIKA SKOZI STOLETJA, Modrijan, Ljubljana 2008, 224 strani. Ob prebiranju knjige sem se spomnil starih ˇ casov, ko sem na Fakulteti za strojniˇ stvo vodil vaje iz matematike. Pogosto so bili ˇ studenti nemirni. Ko pa sem zaˇ cel pripovedovati kakˇ sno zgodbo iz zgodovine matematike, so nenadoma vsi utihnili in prisluhnili ter me celo kaj vpraˇ sali. To najbrˇ z pomeni, da ˇ studente, pa tudi uˇ cence, dijake, uˇ citelje, profesorje in vse, ki imajo opravka z matematiko, le-ta zanima tudi po zgodovinski plati. V slovenˇ sˇ cini je kar nekaj del, ki posebej obravnavajo zgodovino mate- matike, pa tudi nekaj takih, ki ji posveˇ cajo vsaj kak razdelek. Priˇ cujoˇ ca knjiga pa jim je lahko dobrodoˇ sel in koristen dodatek. Bralec bo spoznal, da matematika ni od vˇ ceraj, ampak je, taka kot je, rezultat svojega veˇ cti- soˇ cletnega razvoja, v katerem so bile tudi zablode, tragedije in afere, saj so jo ustvarjali ˇ zivi ljudje. Avtorja knjige najprej povesta, komu in ˇ cemu je knjiga namenjena. To sopredvsemuˇ citeljimatematike,kinajbivneslivpouktudikakˇ snozanimi- vost iz zgodovine matematike. Nato bralca pribliˇ zno tretjina knjige popelje skozi zgodovino matematike, od njenih najstarejˇ sih zaˇ cetkov prek starogr- ˇ ske,kitajske,indijske,arabske,srednjeveˇ skepavsedodanaˇ snjematematike. Naslednji del knjige sestavlja 25 skic, od katerih vsaka obravnava najpo- membnejˇ se mejnike v razvoju matematike, na primer zapise ˇ stevil, razvoj matematiˇ cnih simbolov, teˇ zave pri uvajanju negativnih in kompleksnihˇ ste- vil. Takospoznamorazvojposameznihmatematiˇ cnihpodroˇ cijskozistoletja in glavne ideje, ki so jih omogoˇ cile. Knjiga nas ves ˇ cas opozarja na matematiˇ cno literaturo, kjer lahko naj- 160 Obzornik mat. fiz. 56 (2009) 4