Home
Flashcards
Preview
Graph Theory
Home
Get App
Take Quiz
Create
Network
Destinations with their connecting links
Euler circuit problems
problems questioning routes and backtracking
Graph Theory
the study of circuit and routing problems
graph
collection of one or more points(vertices) and the connections between them(edges)
Vertices
connections on a graph
Vertex
Connection on a graph {singular}
edges
connections on a graph eithier straight or curved
loop
edge that connec ts to itself with only one vertex
adjacent vertices
two vertices ina graph connected by an edge
T/F? A vertex may be adjacent to itself
True
False
True
Degree of a vertex
Total number of edges at a vertex
How do you find the degree of a vertex?
Count the number or segments or arches "coming out" of the vertex
path
route that passes from one vertex to an adjacent vertex, and each edge connecting an adjacent vertex is used, at most, once
Euler path
path that uses every edge of a graph exactly once
circuit
path that ends at the same vertex in which it started
Euler circuit
circuit that uses every edge of a graph exactly once
connected
graph in which you can travel from any vertice to any other in the graph
disconnected
a graph in which is not connected
components
seperate pieces of a graph that cannot be enlarged while remaining connected
bridge
edge in a connected graph, in which the removal of would leave behind a graph that is disconnected
edge-walker algorithm
gives optimal eulerization for a rectangular path
If d is the sum of degrees of all vertices and e is the number of edges in a graph, then: (equation)
d=2e
multigraph
more than one edge connecting two vertice
Connected graph has a Euler Cycle/Circuit
if and only if
each of its vertices have an even degree
Splicing
Is a simple way to make a circuit, rather than using Fleury's Algorithm
Author
m1026258
ID
34708
Card Set
Graph Theory
Description
Graph theory 6.1
Updated
2010-09-15T00:02:05Z
Show Answers
Home
Flashcards
Preview