wykład 6.pdf

6Matematykadyskretna.

Matematykadyskretnatodziedzinamatematyki,którazajmujesi¦badaniemwłasno±cizbiorów

sko«czonychiokre±lonychnanichfunkcji.Wpowi¡zaniuzrachunkiemprawdopodobie«stwama

onazastosowaniewgenetyce,ﬁlogenetyceigenomicenowejdziedziniewiedzywykorzystuj¡cej

metodyinformatykiimatematykidobadaniainformacjizawartejwgenomie.

Wramachmatematykidyskretnejprzedstawimypodstawowepoj¦ciaifaktyzkombinatoryki

iteoriigrafów.

6.1Kombinatoryka

Niech X b¦dziezbioremsko«czonym.Ci¡giemelementówzezbioru X nazywamyfunkcj¦okre±lon¡

nadowolnympodzbiorze I kolejnychliczbnaturalnychINowarto±ciachw X czylika»dejliczbie

zezbioru I przyporz¡dkowanyjestdokładniejedenelementzbioru X .Wtensposóbelementy

zbioru X zostaj¡uporz¡dkowane.Oczywi±cietakichuporz¡dkowa«mo»eby¢wiele.Dlapodkre-

±leniatego,»eelementyci¡gus¡uporz¡dkowaneawi¦cponumerowanenazywasi¦jewyrazami.

Ci¡gmo»naoznaczy¢jako { a k } n k = l . Wtedypierwszymwyrazemonumerze l jest a l aostatnim

onumerze n jest a n czyli I = { l,...,n } . Mo»natak»eokre±li¢ci¡gwypisuj¡cjegoelementy

pisz¡c( a l ,a l +1 ,a l +2 ...,a n )Dlaprzykładurozpatrzmyzbiórliter X = { a,b,c } .Otowszystkie

podzbiorydwuelementowetegozbioru

{ a,b } , { a,c }{ b,c }

orazwszystkieci¡gidwuwyrazoweelementówzezbioru X

( a,a ) , ( a,b ) , ( a,c ) , ( b,b ) , ( b,a ) ,

( b,c ) , ( c,a ) , ( c,b ) , ( c,c ) .

Wsródpyta«,któremo»nazada¢odno±nieci¡gówsko«czonychwybierzmydwa;

z }| {

m · m ·· ...m gdy»pierwszywyrazci¡gu

mo»nawybra¢na m sposobów,drugirównie»na m sposobówitakdalejnaka»dymspo±ród

p miejsc.

owarto±ciachwzbiorze m elementowymczyli m p =

2.Ilejestwszystkichci¡gów p wyrazowychzezbioru m -elementowegogdy m p itakich,

»ewyrazywci¡guniepowtarzaj¡si¦?Innymisłowyilejestfunkcjiró»nowarto±ciowycho

dziedzinie p -elementowejowarto±ciachzezbioru m -elementowego.

Odpowied¹brzmi:Zbiórwszystkichci¡gów p wyrazowychiró»nowarto±ciowychzezbioru

m -elementowegoma

m · ( m − 1) · ( m − 2) · ( m − 3) · ... ( m − ( p − 1))

1.Ilejestwszystkichci¡gów p -wyrazowychowyrazachzezbioru m -elementowego?Czyli ]I = p

a ]X = m .

Odpowied¹brzmi:Jestichtyleilejestwszystkichfunkcjiokre±lonychnazbiorze p -elementowym

= V p m elementów.

Ka»dytakici¡gnazywasi¦wkombinatoryce wariacj¡bezpowtórze« .Wprzypadku

szczególnymgdy m = p mamy

ozn.

V m m =1 · 2 · ... ( m − 1) m ozn.

= m !

Przykład6.1. Odpowiemynapytanie,ilejestwszystkichmo»liwychci¡gówzasadazotowychw

10elementowymfragmencieła«cuchaRNA?

ZbiórzasadazotowychUACGjestczteroelementowy.Naka»dymmiejscuła«cuchaRNAmo»eby¢

dowolnaspo±ródczterechzasadawi¦cwszystkichmo»liwychjesttyleileci¡gów10-wyrazowych

owarto±ciachzezbioruczteroelementowegoczyli4 10 =1048576 .

Ograniczmysi¦terazdoczteroelementowychfragmentówła«cuchaizapytajmyilejest4-elementowych

ła«cuchów,wktórych»adnedwiezasadysi¦niepowtarzaj¡.Jestichoczywi±cie1 · 2 · 3 · 4=4!=24 .

Przyjmijmyteraz,»esłowemnazywa¢b¦dziemydowolnyci¡gliter(znaków)jakiego±alfabetu.

Otokilkapyta«,któremo»napostawi¢odno±nieliczbysłówmaj¡cychokre±lonewłasno±ci.

1.Ileró»nychsłówdziesi¦cioliterowychmo»nautworzy¢zdziesi¦ciuró»nychlitertakabylitery

niepowtarzałysi¦wsłowie?

2.Nailesposobówmo»nawybra¢trójki(nieuporz¡dkowane)niepowtarzaj¡cychsi¦literspo-

±ród10znakówalfabetu?

3.Nailesposobówmo»nawybra¢słowatrzyliteroweoniepowtarzaj¡cychsi¦literachspo±ród

10znakówalfabetu?

4.Ilesłówtrzyliterowychmo»nautworzy¢z10literalfabetu?

Wpierwszejchwilimo»esi¦wydawa¢,»etrzyostatniepytaniadotycz¡tegosamegozagadnienia.

Takjednakniejest.Spróbujmywyrazi¢tepytaniawj¦zykumatematyki.Pierwszepytaniedotyczy

wistocieliczbywszystkichci¡gów10-wyrazowychiró»nowarto±ciowychlubu»ywaj¡cspecyﬁcznej

terminologiikombinatorycznejliczbywszystkich permutacji 10wyrazowych.Jestich

10 =1 · 2 · 3 · ... 7 · 8 · 9 ·· 10=10!=3628800 ,

gdy»ustalenieelementuna j -tejpozycji(gdzie j mo»eby¢dowoln¡liczb¡naturaln¡mi¦dzy1i

9)zmniejszaojedenliczb¦mo»liwo±cispo±ródktórychwybieramyelementnapozycji j +1.

Wdrugimpytaniuchodzioliczb¦wszystkichpodzbiorów3-elementowychzbioru10-elementowego

bezustaleniajakiegokolwiekporz¡dkuichwyst¦powania.Przypomnijmyszkoln¡wiedz¦,chodzio

liczb¦ kombinacji k -elementowychze

zbioru n -elementowego ,oznaczan¡jako C k n ,gdzie k =3a n =10.Uzasadnimy,»eliczba,ozn.

C k n ,kombinacji k -elementowychzezbioru n -elementowegojestrówna

C k n =( n k ) ozn.

= n !

( n − k )! k ! .

V 10

Symbol( n k )totzw.symbolNewtona,któryczytamy” n po k ”.Spróbujmynajpierwznale¹¢liczb¦

wszystkichci¡gów k -wyrazowychoelementachzezbioru n elementowego, n k ,czyliliczb¦

wszystkichwariacji k -wyrazowychzezbioru n -elementowego.Pierwszywyrazci¡gumo»emywy-

bra¢na n sposobówdrugiju»tylkona n − 1sposobówitak k -tywyrazna n − ( k − 1)sposobów.

Terazpozostajeuwzgl¦dni¢,»erozró»niali±myci¡giwktórychwyst¦puj¡tesameelementyw

ró»nejkolejno±ci.Liczb¦wszystkichwariacjibezpowtórze«musimyzmniejszy¢tylerazyilejest

permutacjik-wyrazowych.Wszystkichkombinacjijestzatem

n ( n − 1) · ... ( n − ( k − 1))

k ! = n !

( n − k )! k ! .

Wnaszymprzypadku

C 3 10 := 10 3

7!3! = 1 · 2 · 3 · ... 7 · 8 · 9 ·· 10

(1 · 2 · 3 · ... 7) · 2 · 3

6 =4 · 3 · 10=120 .

Uwa»nyczytelnikzauwa»yłzapewne,»epowy»szerozumowaniezawieraodpowied¹napytanie

trzecie.Słówtrzyliterowychoniepowtarzaj¡cychsi¦literachjesttyleilejestwariacjitrzywyrazo-

wychbezpowtórze«czyli V 10

= 8 · 9 · 10

3 =10 · 9 · 8=720 .

Wpytaniuczwartymchodziza±oliczb¦wszystkichci¡gówtrzywyrazowychowyrazachze

zbioru10-elementowego(literymog¡si¦powtarza¢)czyliliczb¦wszystkichfunkcjiokre±lonychna

zbiorzetrzyelementowymwzbiór10-elementowy.Jestichtyleilejestwszystkichtrzywyrazowych

wariacjizpowtórzeniamizezbioru10-elementowegoczyli10 · 10 · 10=10 3 .

Rozwa»myterazzagadnienieznanejakoproblemkojarzeniamał»e«stw,któreformułujesi¦

nast¦puj¡co:

Ka»dyzokre±lonegozbiorupanówznapewn¡liczb¦pa«.Jakiwarunekmusiby¢spełnionyabyka»dy

panmógłpo±lubi¢pani¡któr¡zna.Przypadekbigamii,wa»nyzbiologicznegopunktuwidzenia,z

górytuwykluczamy.

Powiedzmy,»ezbiórpanówma m elementów.Łatwoznale¹¢warunekkonieczny.Mianowicie,je±li

problemkojarzeniamał»e«stwmapozytywnerozwi¡zanietowszyscypanowiezdowolnego

k -elementowegozbiorupanów1 ¬ k ¬ m musz¡zna¢ł¡cznieconajmniej k pa«.Istotnie,gdyby

takniebyłotodlapewnegopodzbioruzbiorupanówniemo»nabyo»eni¢panówztegopodzbioru

niemówi¡cju»opozostałychpanach.Ciekawejestto,»etenwarunekkoniecznyjestzarazem

warunkiemwystarczaj¡cymcomo»naudowodni¢indukcyjnie.Dowódtegofaktupochodz¡cyod

Halla(1935)mo»naznale¹¢np.wksi¡»ce[ ? ].

Przykład6.2. Czterechkolegów,kolejnoPiotr,Krzysztof,ZenoniMichałpragnieo»eni¢si¦.

Michałznawszystkiepanierozwa»aneprzeztychpanówtoznaczyDorot¦,Iren¦,Ani¦iRenat¦.

Ka»dyspo±ródtrzechpierwszychpanówznatylkoDorot¦iIren¦.Sytuacj¦przedstawiarysunek

zwanygrafem.

= 10!

Rys.6.1.Cał¡informacj¦owzajemnychznajomo±ciachzawierapowy»szygraf.

SkoroPiotr,KrzysztofiZenonznaj¡wspólnietylkoDorot¦iIren¦problemmo»narozstrzygn¡¢

honorowotylkopoprzezpojedynek,alboposzerzeniegronaznajomych.

Przedpodobnymzagadnieniemstajedyrektordobieraj¡ckompetencjepracownikówdlawyko-

naniaokre±lonychprac.Umiej¦tno±¢wykonaniadanejpracyprzezdanegopracownikaodpowiada

mał»e«stwuzpoprzedniegoprzykładuachodziterazotoabyka»demupracownikowiprzydzieli¢

prac¦któr¡znaiabywszyscybylizaj¦ci.Tegotypuproblemjestprostyiniewymagaznajomo±ci

matematykigdyliczbapracownikówipracjestniewielka,alegdypracownikówjestnp.2000to

powy»szetwierdzenieHallaprzydajesi¦,aobliczeniamusiwykona¢programkomputerowy.

6.2Grafy

Grafynale»¡doobiektówmatematycznychnajcz¦±ciejwykorzystywanychwzastosowaniach.Po-

jawiaj¡si¦onewekonomiinp.wzagadnieniachtransportowych.Wsocjologiisłu»¡dobadania

ró»nychrelacjispołecznychawinformatycedotworzeniastrukturbazdanych.Wchemiiza

pomoc¡grafumo»naprzedstawi¢schematatomówiwi¡za«chemicznychwcz¡steczkachnppo-

limerach.WﬁzycediagramyFeynmana(pewnegotypugrafy)s¡modelamioddziaływa«cz¡stek

elementarnych.Wbiologiizkoleidrzewa,szczególnytypgrafów,słu»¡doprzedstawianiaiana-

lizypokrewie«stwapomi¦dzyró»nymijednostkamitaksonomicznymi.Drzewaﬁlogenetyczneto

podstawowastrukturawewspółczesnejtaksonomiiigenetyce.Grafyreprezentuj¡tak»esposób

przechowywaniaiwzajemnerelacjepomi¦dzyinformacjamizapisanymiwposzczególnychcz¦-

±ciachgenomu.Wekologiigrafyprzedstawiaj¡siecitroﬁczneametodyteoriigrafówwykorzystuje

si¦dobadaniaspecyﬁcznierozumianejstabilno±ciekosystemów[ ? ].Zapomoc¡grafumo»nare-

prezentowa¢ibada¢siecineuronowe.Wlingwistycegrafysłu»¡doanalizystrukturgramatycznych

iwykorzystywanes¡doautomatycznejweryﬁkacjipoprawno±cizda«wró»nychj¦zykach.

Deﬁnicja1Grafem nazywamyobiektskładaj¡cysi¦zpewnegozbioruelementów(sko«czonego

lubniesko«czonegoprzeliczalnego)zwanychdalej wierzchołkami oraz kraw¦dzi ł¡cz¡cychwierz-

chołki.Bardziejprecyzyjnierzeczujmuj¡cgrafokre±lamyjakopar¦ ( V,E ) gdzieVtozbiórwierz-

chołkówaEtozbiórkraw¦dzi.Zwi¡zekpomi¦dzywierzchołkamiikraw¦dziamiokre±lafunkcja,

któraka»dejkraw¦dziprzyporz¡dkowujepar¦punktów-wierzchołkówcograﬁcznieprzedstawiamy

ł¡cz¡cpar¦wierzchołkówodcinkiem.

Wartopodkre±li¢,»e

• kraw¦d¹mo»eł¡czy¢danywierzchołekznimsamym,tak¡kraw¦d¹nazywamyp¦tl¡,

• wi¦cejni»jednakraw¦d¹mo»eł¡czy¢dwawierzchołki.

Grafnazywamy skierowanym (digraph,odang.directedgraph)je±likraw¦d¹jestuporz¡dkowan¡

par¡wierzchołkówcozaznaczasi¦zwyklezapomoc¡strzałki.Ka»dejkraw¦dzimo»naprzyporz¡d-

kowa¢pewn¡liczb¦(np.wyra»aj¡c¡odległo±¢mi¦dzywierzchołkamilubsił¦relacjimi¦dzynimi),

takigrafnazywasi¦ grafemzwagami lub grafemobci¡»onym .Zgrafamispotkali±mysi¦ju»

przygraﬁcznymprzedstawianiurelacjiwprowadzonejwpewnymzbiorze(por.Rozdz.2.8.)Wtedy

elementytegozbiorutowierzchołkigrafuakraw¦d¹skierowanagrafuł¡cz¡cadwawierzchołki

okre±laczydanaparaelementówtegozbiorujestwrelacjiczynie.Je±liwyst¦puj¡p¦tletorelacja

jestzwrotnaaje±liprzyka»dejkraw¦dził¡cz¡cejwierzchołek A z B wyst¦pujekraw¦d¹ł¡cz¡ca

B z A torelacjajestsymetryczna.

Rys.6.2.a)Grafskierowany,któryokre±larelacj¦cz¦±ciowegoporz¡dkuwzbiorze { A,B,C,D } ,

b)Relacjarównowa»no±ciwzbiorze { A,B,C,D } .

Otokilkaproblemówspozamatematyki,wktórychpojawiaj¡si¦grafy.

Problem1. Rozpatrzmyzbiórwszystkichmiastwwojewództwiemazowieckim.Tworz¡onewierz-

chołkigrafu.Mi¦dzyka»dymidwomamiastamiwybieramydrog¦główn¡ł¡cz¡c¡je.Wybrana

drogaokre±lakraw¦d¹grafu.Pewnaﬁrmamarozmie±ci¢przyka»dejdrodzegłównejł¡cz¡cejdwa

miastabilbordreklamowy.Chodziotoabyzminimalizowa¢kosztyiwybra¢tak¡tras¦pomi¦dzy

miastamiabyka»dyodcinekdrogimi¦dzydwomamiastamiprzeby¢tylkorazipowróci¢domiasta

zktóregosi¦rozpocz¦ło.Jesttopytanieoistnienietzw. cykluEulera wgraﬁe,którerozwa»ymy

wdalszejcz¦±ciwykładu.Innepodobnedotegozadanieotrzymamywzbogacaj¡cpowy»szygraf

owagiokre±laj¡ceodległo±cimi¦dzymiastami.Terazmo»emyposzukiwa¢takiejtrasyabyka»dy

odcinekpomi¦dzydwomamiastamiprzeby¢cho¢byraziprzejecha¢ł¡cznienajmniejkilometrów.

Tegotypuproblemjestznanywliteraturzejakozadaniechi«skiegolistonosza.

Problem2. Rozwa»myzadanie,którepozorniejestpodobnedopoprzedniego.Przyjmuj¡czbiór

miast-wierzchołkówgrafuidróg-kraw¦dzijeł¡cz¡cychtakjakpoprzednio,znale¹¢tak¡tras¦aby

odwiedzi¢ka»dezmiastdokładniejedenraz.Tak¡tras¦nazywasi¦ cyklemHamiltona wgraﬁe.

Problem3. Wjakim±taksonienp.rodzajuwyst¦puje10gatunków.Ka»dyznichmaswojego

ewolucyjnegopoprzednikatenzkoleiswojegopoprzednikaitd.Ka»dygatunekspo±ródtychdzie-

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: