MMW - GRAPH

Graph

Vertices/nhodes and edges

Simple graph

less than or equal to 2 numbers of degree only per vertices

Complete graph

edge connecting every pair of vertices

Null or disconnected graphs

degree of each vertex is zero

Graph coloring

to easily identify boundaries. The adjacent have different color

Chromatic Number

least number of colors that is used

2-colorable graph theorem

2-colorable, simple, no odd number of vertices

four-color theorem

planar graph

Graph coloring

• Vertex

• Edge

• Face

Path

alternate sequence of vertices and edges, no repeated edges and vertices

Circuit or Cycle

begins and end with the same vertex

Relationship between vertices, degree, and edges

K = n(vertices)

deg = n -1

e = ½ n(n-1)

Euler

Edges

Hamilton

Vertices

Euler

Euler path OR euler circuit

Hamilton

Hamilton path AND Hamilton circuit

Euler Path

2 odd degree in vertices, the beginning and end.

Euler circuit/Eulerian

closed path, all vertices has even degree

Neither Euler path or circuit

more than 2 odd degree in vertices

Hamilton Path

passing through vertex exactly once

Hamilton cycle/Hamiltonian

has the same starting and ending. A complete graph with more than 2 degree (K =(n-1)!)

Two hamiltonian

pass same vertices in same order

Dirac’s Theorem

ave. degree > ½ of vertices

Trees

graph, any two vertices are connected by one path. NO CIRCUITS, CONNECTED GRAPHS, EVERY EDGE IS A BRIDGE

Forest

undirected, disconnected, acyclic graph. It is by connecting or bridging of tree

Spanning tree (Kruskal Algorithm)

edge with lowest weight, doesn’t form a circuit, and repeat until all vertices have been connected

Fleurg’s Algorithm

1. no odd vertices → start at any vertex

two odd vertices → start either

2. trace → one per edge only

3. bridge → last option to pass trough

Loop

edge connecting a vertex to itself

Adjacent

two vertices joining with an edge

Equivalent

different shapes, same vertices connected in the same way

Connected

there is a path that joins two vertices

Bridge

when you remove it, it makes the graph disconnected

Degree

number of edges attached to the vertex

Planar

no edges cross. This means that any 2 edges can meet only at an endpoint/vertices