Terminology: degree - of a vertex is the number of edges that intersect that vertex. even vertex - has an even number of edges that intersect it odd vertex - has an odd number of edges that intersect it loops - are considered to be two edges emanating from the vertex adjacent vertices - have at least one edge connecting them path on a graph - a sequence of adjacent vertices and the edges connecting them that uses no edge more than once. A path have to include all of the vertices or doesn’t edges. circuit - a path that begins and ends at the same vertex. The one below is given by A, B, C, E, A. Connected Graph Disconnected Graph Bridge is an edge on a connected graph that, if removed, makes the graph – disconnected. Ex. Use the graph below to answer the following: (a) List the odd vertices. (b) List the even vertices. (c) What vertex has a loop? (d) Are there any bridges?
Terminology: degree - of a vertex is the number of edges that intersect that vertex. even vertex - has an even number of edges that intersect it odd vertex - has an odd number of edges that intersect it loops - are considered to be two edges emanating from the vertex adjacent vertices - have at least one edge connecting them path on a graph - a sequence of adjacent vertices and the edges connecting them that uses no edge more than once. A path doesn’t have to include all of the vertices or edges. circuit - a path that begins and ends at the same vertex. The one below is given by A, B, C, E, A. Connected Graph Disconnected Graph Bridge – is an edge on a connected graph that, if removed, makes the graph disconnected. Ex. Use the graph below to answer the following: (a) List the odd vertices. (b) List the even vertices. (c) What vertex has a loop? (d) Are there any bridges?
14-1%20Basic%20Concepts%20of%20Graph%20Theory.docx