MMW Lesson 5: Simple Graph

A ____________ is a collection of points called vertices or nodes, and line segments or curves called edges that connect the vertices

Graph

A Graph is a collection of points called _________ or ________, and line segments or curves called ________ that connect the vertices

vertices
nodes
edges

A ____________ is an edge connecting a vertex to itself

loop

A _________________ is a graph that has an edge connecting every pair of vertices

complete graph

Two vertices are ___________ if there is an edge joining them

adjacent

Graphs are considered as _____________ if they have same vertices connected in the same way

equivalent

A ____________ is an alternating sequence of vertices and edges. it can be seen as a trip from one vertex to another using the edges of a graph

path

If a path begins and ends with the same vertex, it is a CLOSED PATH or a __________ or __________

circuit
cycle

A graph is _____________ if for any two vertices, there is AT LEAST ONE PATH THAT JOINS THEM

connected

A _____________ is an edge that when you remove makes the graph disconnected

bridge

The _____________ of a vertex is the number of EDGES attached to it

degree

__________ or ______________ is when the degree of each vertex is ZERO

Null or Disconnected Graph

__________________ is when the loop connects vertex A to itself. The degree of the loop is 2

Graph with a loop

One of the subjects studied by mathematicians is _______________. The idea is to color the vertices or edges of a graph in such a way that adjacent vertices or concurrent edges are different colors.

graph coloring

The smallest number of colors required to color the vertices of a graph is the ________________ of the graph

chromatic number

______________________ - a graph that is 2-colorable if and only if it has no circuits that consist of odd number of vertices

2-colorable graph theorem

___________________ - the chromatic number of a PLANAR GRAPH is at most 4

Four-color theorem

____________________ is a way of coloring the vertices of a graph that no two adjacent VERTICES share the same color

Vertex coloring

An _________________ assigns a color to each EDGE so that no two adjacent EDGES share the same color

edge coloring

A ___________________ of a planar graph assigns a color to each FACE or REGION so that no two faces that share a boundary have the same color

Face coloring

A _________ can be represented by a graph with the different regions as VERTICES. Two regions are ___________ if they share part of their boundaries

map
adjacent

The graph representing a map is __________. Hence, it needs ONLY 4 COLORS

planar

_______________ is a path that passes through every edge EXACTLY ONCE ONLY. A path that contains ALL THE EDGES of the graph. It begins and ends with the ODD-DEGREE VERTICES

Euler path

A graph has an ______________ if and only if no more than two of its vertices have odd degree

Euler path

An _____________ of a graph is a closed path that contains all the edges of the graph

Euler circuit

A graph that has an Euler circuit is called an ___________

Eulerian

A ______________ is Eulerian if and only if EACH VERTEX HAS AN EVEN DEGREE

connected graph

If _________________, the graph has at least ONE EULER CIRCUIT (which is by definition also as Euler path). An Euler circuit can start at ANY VERTEX.

all vertices are even

If ___________________, the graph has NO EULER CIRCUITS but at least ONE EULER PATH. The path must begin at ONE ODD VERTEX and end at the other ODD VERTEX.

exactly two vertices are odd

If there are __________________, the graph has NO EULER PATH and NO EULER CIRCUITS

more than two odd vertices

Before using _________________, make sure you’ve used Euler’s Theorem to confirm that the graph has an Euler path or Euler circuit

Fleury’s Algorithm

A ________________ of a graph is a path passing through each VERTEX of the graph exactly once. If the path is closed, it is called a ____________________. If a graph has a Hamiltonian cycle, it is called ________________.

Hamiltonian path
Hamiltonian cycle
Hamiltonian

Every COMPLETE GRAPH with more than TWO VERTICES has a _________________. Furthermore, the number of Hamiltonian circuits in a complete graph with n vertices is (n-1)!

Hamiltonian circuit

_______________________ are the same if they pass through the SAME VERTICES in the SAME ORDER, regardless of the vertex where they begin and end

Two Hamiltonian circuits

A  _______________ is a graph in which ANY TWO VERTICES are connected by EXACTLY ONE PATH

Tree

A tree has no ___________
Trees are _________ graphs
Every edge in a tree is a __________

A tree with n vertices has exactly n-1 edges

circuits
connected
bridge

A ________________ is an undirected, disconnected, acrylic graph. IN other words, a disjoint collection of trees.

Forest

A disjoin collection of trees is known as ___________

forest

Each component of a forest is _________

Tree

A __________________ for a graph is a tree that results from the removal of as many edges as possible from the original graph without making it disconnected

spanning tree

A __________________ for a weighted graph is the spanning tree for the graph that has the SMALLEST POSSIBLE SUM OF THE WEIGHTS

minimum spanning tree

A ____________________ must have ONE FEWER EDGE than the NUMBER OF VERTICES

minimum spanning tree

________________ is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which

1. form a tree that includes every vertex

2. has the minimum sum of weights among all the trees that can be formed from the graph

Prim’s algorithm

A graph is ______________ if it can be drawn is such a way that no edges cross. This means that any two edges can meet only at an endpoint. 

planar