Graph Theory
Home > Flashcards > Print Preview
The flashcards below were created by user
m1026258
on
FreezingBlue Flashcards. What would you like to do?

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

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

edgewalker 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