March 20 2024 Section 1 4 Trees Spanning trees def a tree is connected gran in which every edge is a bridge a V B C I D E F CD is a bridge also DE DF are bridges examples I tree B D a Spanning tree is a tree that is created from another gragh While maintaining a path from any Vertex to any other Vertex must contain NO Circuits examples find spanning trees for A A A B c D E F G B C B C not a tree can we remove anything to make it a tree I D J E D E remove EB CG find Spanning trees for B C F now a tree D I G A I F D E B I G C H A E D B F A I I E A E a minimum cost spanning tree is Spanning tree We find this by using Kruskal s Algorithm the least expensive Kruskal s Algorithm 1 Choose any edge of minimum cost to start 2 Choose an edge of minimum cost that does not create a circuit 3 repeat Step 2 until you have a spanning tree example for the weighted graph shown What is find a minimum cost spanning tree the minimum cost 1 C I A 1 2 2 3 I F B D 4 2 6 5 2 G A C B D E I F G AB AC BD DF EG DG 1 2 2 2 4 Sum is 12 min Cost is 12 for a fair die the possible outcomes are 1 2 3 4 5 6 II of times rolled F 2 7 3 d 5 4 5 S 4 6 7 total 36 P 1 5 P 2 56 P 3 5 5 P 4 56 I P 5 36 P b 5 the Law of Lange numbers the relative frequency of an outcome over the long run is more accuratley predictable than individual events or a few events relative frequency is PLE the theoretical probability of an event P E of outcomes favorable to F total of possible outcomes by the law of large numbers as you repeat an expirament a lot of times the empirical probability will get close to the theoretical probability find the theoretical prob Pleven wi fair die 3 I P rolling an 8 0 P rolling less than 7 Joice st P drawing ace of spades P 2Clubs 2 P drawing a 10 P heart Club O P heart Or club probability of prob of rolling a T with one die an event that cannot occur in 0 April 3rd 2024 probability of an event that must occur is 1 prob of rolling a less than 7 every probability in a between 081 inclusive 0 P E 1 1 the sum of the probabilities of all possible outcomes is 1 the prob of drawing a 10 from a standard deck of Cards is P O S is whats the prob of drawing a card that is not a IO Phot 0 1 POS 1 1 1 B as opposed to P not 10 12 12 12 12 52 52 whats the prob of landing on Red it Ps E P red green die i E 2 z z 7 1 a cooler is filled wh 50 cans of soda 25 come 15 LaCroix 5 dr popper 5 Syrite What is the prob of picking a coke P coke E P Lacroix 5 P dr yep 50 P sprites S 25 5 1 a roulette wheel has 38 slots numbered of which 18 are red 18 are black I are green Tony bought 3800 Chips for 1 each of the wheat If he wind be doubles P B h 1800 P R i 1800 net ch P G i 30 g his of a is on one red slot chips He placed J his so woextingwins or netof for all spins combined for 3000 spins to sento o a lossess to be P G 00 loses o net of 200