INB371 Week 10 L.doc

4 Pages
Unlock Document

Queensland University of Technology
Malcolm Corney

Lecture 10 INB371 Graphs Graphs are important in CS cause they can represent any relationship. The key to solving problems is to think of them in terms of graphs, e.g. a GPS, showing you a graph of point a to point b. There are lots of algorithms to solve these sorts of problems, such as the shortest path algorithm by Djikstra and the Minimum Spanning Tree algorithm. Euler’s solution to the Konigsberg bridge problem brought about Graph Theory, an entire new branch of mathematics. He did this by removing all physical properties of the problem, leaving just the nodes and bridges. When we have more than one pair between two nodes, it’s called a ‘parralell edge’. If a node has an edge that connects to itself it’s called a ‘loop’. A sequence of edges that connects two nodes is called a path. Paths can be designated by the paths it crosses (wxyz), or BCDAC ( the vertices it passes through). If a graph has parallel edges and you designate a path by the vertices it passes through, it cannot determine which edge it goes down. A path is called ‘closed’ if it starts and finishes at the same vertices. If it doesn’t repeat any edge it’s called a ‘circuit’ or ‘cycle’. If no vertex is repeated the path is a ‘simple cycle’. Graphs can be categoriesd into undirected and directed. In undirected, the edges don’t indicate a direction, and a directed graph does indicate direction. You can only go that direction down the edge. A Subgraph consists of a subset of the graphs vertices and a subset of the graphs edges. A weighted graph is a graphs whos edges have a weight , e.g. it costs more to go down that edge. Vertices of a graph are ‘adjacent’ if they’re connected by an edge. A graph is ‘connected’ if there’s a path between each pair of distinct vertices (e.g. no vertices on their own with no edges). A graph is complete if there’s an edge between each pair of vertices. A degree of a vertex is the number of edges attached to it. A loop counts as two edges. An Euler Path is a path that uses every edge of a graph exactly once, starting and ending at different vertices. An Euler circuit is a circuit that uses every edge of a graph exactly once, ending on the same vertex it started on. Criteria for Euler Paths For every vertex on a particular graph other than the start/finish vertex, the path enters the vertex the same number of times it leaves the vertex. Therefore, all vertices other than the two endpoints of P must be even vertices, and the endpoints of the path are odd vertices. Euler Circuits For every vertex in the graph, each edge having v as an endpoint shows up exactly once in the circuit. The circuit enters vertex same number of times it leaves a vertex, so vertex has degree 2s. therefore v must be an even vertex. You can easily find out if a euler path or circuit exists by counting the amount of odd vertices. There are four different representations of graphs: Unweighted/Undirected Weighted/Undirected Unweighted/Directed Weighted/Directed There are two data structures to represent a graph,
More Less

Related notes for INB221

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.