Subgraphs : The subgraph G induced by V' is the graph (V',E').
Induced : The subgraph G' has everything taken from G.
A chain : it's a special graph where two nodes have a degree of one and all the other ones have a degree of two
A star : one node has n-1 neighbours and the other ones have a degree of one.
Tree : An undirected graph is said to be a tree if it contains no-cycle (acyclic) and is connected.
Binary tree : A binary tree is a tree where each node has a parent (except the root) and up to two children. A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
A binary tree : it's a special tree where each parent has one or two children.
A multigraph : it's a graph that can have multiple edges between two same points.
A self loop : it's when a node loops on itself.
A bipartite graph : it's a graph who can be coloured with two colours such that two nodes of the same colour don't have any edges in commun.
A weighted graph : it's a graph such that each edge has a weight.
A directed graph : it's when the edges have a direction.
A rooted tree : A rooted tree is a tree where there is a notion of the "top" node, which is called the root. Thus, each node has one parent and has any number of children.
Forest : A forest is an undirected graph which contains no cycle.
DAG: Directed Acyclic Graph
Complete graph : A graph is said to be complete if there is an edge between every pair of vertices
Bipartite graph : A graph is said to be bipartite if the vertices can be split into two sets V1 and V2 such there are no edges between two nodes of V1 or two nodes of V2.
Acyclic : no cycle
No comments:
Post a Comment