Please enable JavaScript.
Coggle requires JavaScript to display documents.
fundamentals of graphs - Coggle Diagram
fundamentals of graphs
undirected graph(graph w
here edges have no diection,meaning connection between vertices work both ways)
properties
degree(number of edges incident to a vertex)
pendent(vertex has one degree)
isolated(vertex has xero degree)
adjacent vertiex(vertex connected by an edge)
simple graph(graph with no loops and no multiple edges)
bipartile graph(vertex split into two graphs and edges go between the groups)
cycle(vertices form a closed loop)
wheel(cycle with one extra center point connected to all other)
complete bipartile(every vertex in one group connects to every vertex in other group)
complete graph(every vertex is connectedx to every other evrtex)
multigraph(graph that allows multiple edges between the same vertixes)
regular graph(all vertex has same degree)
finite graph(graph with endless vertex & edges)
complementary graph(graph formed by connecting nin adjacent vetices of the original)
directed graph( edges have direction)
directed simple graph(a directed graph with no multiple edges between the same ordered pair of vertices and no loops)
directed multi graph(a directed graph that allows multiple directed edges between the same ordered pair of vertices and may include loops)
properties
adjacent from(a vertex v is adjacent from vertex u if there is a directed edge from u to v)
adjacent to(a vertex u is adjacent to vertex v if there is a directed edge from u to v)
indegree(the number of directed edges coming into a vertex)
outdegree(the number of directed edges going out of a vertex)
infinite graph(graph with limited edges and vertex)
properties of graph
representation of graphs
adjacency matrix(a table that shows connections between every pair of vertices)
adjacency list(a list that shows which vertices are conne ted to each vertex)
incidence matrix(a table that shows which vertices are connected to which edges)
operations and concepts
adding edge(add new edge between vertex)
subgraph(graph formed from subset of evrtex and edge)
removing edge(deletes edge from graph)
removing vertex(deletes vertex from the grph)
adding vertex(add vertex between edges)
union of 2 graph(combine edges and vertex of 2 graph)
connectivity of the graph
edge connectivity
edge cut(set of edges whose removal diconnects graph
cut edge(edge whose removal increase the number of connected components)
vertecx connectivity(
vertex cut(set of vertices whose removal disconnects graph
cut vertex(vertex whose removal increase the number of connwected components
basic definitions
hamiltonian pathpath visiting every vertex exactly once()
euler path(path visiting every edge exactly once)
connected components(maximal cionnected subgraphs)
connected graph(all vertices are reachable from one another)
simple path(path with no repeated vertices)
circuit(a closed path starting and ending at the same vertex)
path(a sequence of distinct vetices connected by edges)