Discrete Math For Computing IIContact InformationCourse OutlineCourse ABET ObjectivesEvaluationHomeworksGradingLikely Letter GradesScheduleCheatingSpring Break !Graph TheoryVarying Applications (examples)Topics CoveredDefinitions - GraphDefinitions – Edge TypeSlide 17Definitions – Graph TypeSlide 19Slide 20Slide 21Slide 22Slide 23Terminology – Undirected graphsTerminology – Directed graphsTheorems: Undirected GraphsSlide 27Theorems: directed GraphsSimple graphs – special casesSlide 30Slide 31Slide 32Bipartite graphsComplete Bipartite graphsSubgraphsSlide 36RepresentationRepresentation- Incidence MatrixSlide 39Representation- Adjacency MatrixSlide 41Slide 42Slide 43Representation- Adjacency ListGraph - IsomorphismSlide 46ConnectivityConnectivity – PathSlide 49Connectivity – ConnectednessSlide 51Slide 52Slide 53Slide 54Isomorphism - revisitedCounting PathsSlide 57Slide 58The Seven Bridges of Königsberg, GermanySlide 60Slide 61Euler - definitionsSlide 63Euler - theoremsEuler – theorems (=>)Slide 66Slide 67Slide 68Slide 69Euler CircuitSlide 71Homework 1Hamiltonian GraphSlide 74This one has a Hamiltonian path, but not a Hamiltonian tour.Slide 76Slide 77Slide 78Shortest PathShortest-Path ProblemsOptimal SubstructureNegative Weights and Cycles?Shortest Path TreeRelaxationDijkstra's AlgorithmDijkstra’s ALgorithm Solution to Single-source (single-destination).Dijkstra’s ExampleSlide 88Slide 89Dijkstra’s AlgorithmTraveling Salesman ProblemPlanar GraphsSlide 93Slide 94Slide 95Slide 96Slide 97Slide 98Slide 99Slide 100Region DegreeSlide 102Slide 103Slide 104Slide 105Slide 106Graph Coloring ProblemVertex Coloring ProblemSlide 109Vertex Covering ProblemDiscrete Math For Computing IIMain Text: Topics in enumeration; principle of inclusion and exclusion, Partial orders and lattices. Algorithmic complexity; recurrence relations, Graph theory.Prerequisite: CS 2305"Discrete Mathematics and its Applications" Kenneth Rosen, 5th Edition, McGraw Hill.Contact InformationB. PrabhakaranDepartment of Computer ScienceUniversity of Texas at DallasMail Station EC 31, PO Box 830688Richardson, TX 75083Email: [email protected]: 972 883 4680; Fax: 972 883 2349URL: http://www.utdallas.edu/~praba/cs3305.htmlOffice: ES 3.706Office Hours: 3.30 – 4.00 pm & 5.15 – 6pm. Tuesdays;5.15 – 6pm ThursdaysOther times by appointments through emailAnnouncements: Made in class and on course web page.TA: TBA.Course OutlineSelected topics in chapters 6 through 9.Chapter 6: Advanced Counting Techniques: recurrence relations, principle of inclusion and exclusionChapter 7: Relations: properties of binary relations, representing relations, equivalence relations, partial ordersChapter 8: Graphs: graph representation, isomorphism, Euler paths, shortest path algorithms, planar graphs, graph coloringChapter 9: Trees: tree applications, tree traversal, trees and sorting, spanning treesCourse ABET ObjectivesAbility to construct and solve recurrence relationsAbility to use the principle of inclusion and exclusion to solve problemsAbility to understand binary relations and their applicationsAbility to recognize and use equivalence relations and partial orderingsAbility to use and construct graphs and graph terminologyAbility to apply the graph theory concepts of Euler and Hamilton circuitsAbility to identify and use planar graphs and shortest path problemsAbility to use and construct trees and tree terminologyAbility to use and construct binary search treesEvaluation2 Mid-terms: in class. 75 minutes. Mix of MCQs (Multiple Choice Questions) & Short Questions.1 Final Exam: 75 minutes or 2 hours (depending on class room availability). Mix of MCQs and Short Questions.2 - 3 Quizzes: 5-6 MCQs or very short questions. 15 minutes each.Homeworks/assignments: 3 or 4 spread over the semester.HomeworksEach homework will be for 10 marks.Homeworks Submission:Submit on paper to TA/Instructor.GradingHome works: 5%Quizzes: 10%Mid-terms : 50% Final: 35%Likely Letter GradesA-, A, A+: 90 - 100% B-, B, B+: 80 - 90% C-, C, C+: 70 - 80%D-, D, D+: 60 - 70%F: Below 60% Class average will influence above the ranges.ScheduleQuizzes: Dates announced in class & web, a week ahead. Mostly just before midterms and final.Mid-term 1 : February 10, 2005Mid-term 2: March 24, 2005Final Exam: 11am, April 26, 2005 (As per UTD schedule)Subject to minor changesQuiz and homework schedules will be announced in class and course web page, giving sufficient time for preparation.CheatingAcademic dishonesty will be taken seriously.Cheating students will be handed over to Head/Dean for further action.Remember: home works (and exams too !) are to be done individually.Any kind of cheating in home works/exams will be dealt with as per UTD guidelines.Spring Break !Conference Travel in the week starting March 1st.Propose a 2-hour make up class (with 15 minute break between the hours) on a Monday morning ?Graph TheoryChapter 8Varying Applications (examples)Computer networksDistinguish between two chemical compounds with the same molecular formula but different structuresSolve shortest path problems between citiesScheduling exams and assign channels to television stationsTopics CoveredDefinitions TypesTerminologyRepresentationSub-graphsConnectivityHamilton and Euler definitionsShortest Path Planar GraphsGraph ColoringDefinitions - GraphA generalization of the simple concept of a set of dots, links, edges or arcs. Representation: Graph G =(V, E) consists set of vertices denoted by V, or by V(G) and set of edges E, or E(G)Definitions – Edge TypeDirected: Ordered pair of vertices. Represented as (u, v) directed from vertex u to v.Undirected: Unordered pair of vertices. Represented as {u, v}. Disregards any sense of direction and treats both end vertices interchangeably.u vu vDefinitions – Edge TypeLoop: A loop is an edge whose endpoints are equal i.e., an edge joining a vertex to it self is called a loop. Represented as {u, u} = {u}Multiple Edges: Two or more edges joining the same pair of vertices. uDefinitions – Graph TypeSimple (Undirected) Graph: consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called edges (undirected) Representation Example: G(V, E), V = {u, v,