Exam 4 Flashcards
A vertex with no edges
Isolated Vertex
More than one edge connecting two vertices
Parallel Edges
The number of times that a vertex is an endpoint
Degree of a vertex
A graph with no loops or parallel edges
Simple Graph
A graph that can be partitioned into 2 sets for which every edge connects vertices in different sets
Bipartite Graph
The complete bipartite graph on m,n
Kmn
A maximal connected subgraph
Connected Component
A finite alternating sequence of adjacent vertices and edges
Walk
A walk that does not contain a repeated edge
Path
A path that does not contain a repeated vertex
Simple Path
A walk that begins and ends on the same vertex
Closed Walk
A closed walk that does not contain a repeated edge
Circuit
Graphs with a 1-1 function such that vertices x and y are joined by an edge and so are f(x) and f(y)
Isomorphic
1-1 function between two graphs
Isomorphism
A property of a graph that doesn’t change under isomorphism
Invariant
A circuit that does not have any other repeated vertex except the first and last
Simple Circuit
Circuit which contains every vertex and every edge
Euler Circuit
If a graph has an Euler circuit then every vertex has an _____ degree
Even (degree of every vertex in _______)
If every vertex is even and the graph is connected, then the graph has _____________
An Euler Circuit (what does this say about connectedness and degrees?)
A sequence of adjacent edges and vertices that starts at v, ends at w, and passes through every vertex and along every edge exactly once
Euler Path
Connected graph that has no non-trivial circuits
Tree
for a tree, the number of edges = __________
The # of vertices in the tree -1
A ________ is contained in a tree
Circuitless Graph (is contained in what?)
connected AND e=v-1
connected AND circuitless
circuitless AND e=v-1
Properties of a tree
A subgraph of a graph that is a tree which includes every vertex
Spanning Tree
Graph with numeric weights attached to the edges
Weighted Graph
Spanning tree of the least possible weight
Minimal Spanning Tree
Algorithm which adds vertices of lowest possible value that do not close circuits
Kruskal’s
Algorithm that starts with a single vertex, then adds an edge and vertex at each step of minimal weight and does not close a circuit
Prim’s
Isolated Vertex
A vertex with no edges
Parallel Edges
More than one edge connecting two vertices
Degree of a vertex
The number of times that a vertex is an endpoint
Simple Graph
A graph with no loops or parallel edges
Bipartite Graph
A graph that can be partitioned into 2 sets for which every edge connects vertices in different sets
Kmn
The complete bipartite graph on m,n
Connected Component
A maximal connected subgraph
Walk
A finite alternating sequence of adjacent vertices and edges
Path
A walk that does not contain a repeated edge
Simple Path
A path that does not contain a repeated vertex
Closed Walk
A walk that begins and ends on the same vertex
Circuit
A closed walk that does not contain a repeated edge
Isomorphic
Graphs with a 1-1 function such that vertices x and y are joined by an edge and so are f(x) and f(y)
Isomorphism
1-1 function between two graphs
Invariant
A property of a graph that doesn’t change under isomorphism
Simple Circuit
A circuit that does not have any other repeated vertex except the first and last
Euler Circuit
Circuit which contains every vertex and every edge
Even (degree of every vertex in _______)
If a graph has an Euler circuit then every vertex has an _____ degree
An Euler Circuit (what does this say about connectedness and degrees?)
Connected, every vertex has even degree
Euler Path
A sequence of adjacent edges and vertices that starts at v, ends at w, and passes through every vertex and along every edge exactly once
Tree
Connected graph that has no non-trivial circuits
The # of vertices in the tree -1
Number of edges in a tree
Circuitless Graph (is contained in what?)
A tree
Properties of a tree
connected AND e=v-1
connected AND circuitless
circuitless AND e=v-1
Spanning Tree
A subgraph of a graph that is a tree which includes every vertex
Weighted Graph
Graph with numeric weights attached to the edges
Minimal Spanning Tree
Spanning tree of the least possible weight
Kruskal’s
Algorithm which adds vertices of lowest possible value that do not close circuits
Prim’s
Algorithm that starts with a single vertex, then adds an edge and vertex at each step of minimal weight and does not close a circuit
