null

US

477597

A graph is made up of points (nodes/vertices) joined by lines (edges/arcs).

Weighted Graphs/Networks have a number on Each Arc

Digraphs/Directed Graphs have Directed Edges

Complete Graph's ertices are All Directly Connected

Subgraphs are bits of another graph rub out bits of a graph you get a subgraph A subgraph of graph G is a graph where all the vertices and edges belong to G

Paths are routes in the graph that don't repeat any vertices

A Path is a sequence of edges that flow on, end to end

A Cycle/Circuit is a path that brings you back to your starting point a closed path the end vertex is the same as the start vertex

Trees are graphs with no cycleshave to be connected graphs

Spanning Trees are subgraphs that are also trees have to include all the vertices the number of edges is one less than the number of vertices

The Degree of a Vertex is the number of lines coming off it The degree/valency of a vertex (node order) is the number or edges connected to it a vertex with an odd degree is odd, one with an even degree is even

The sum of the degrees is always double the number of edges, so it is always even.

Adjacency/Incidence Matrices show the number of links between verticesto draw from a graph, count the number of direct connections from the vertex at the left of the row to the vertex at the top of the column

Distance Matrices show the weights between vertices To draw, write down the weight between the two vertices, only including direct links weights with directed edges only get written once

Graphs

Want to create your own Notes for **free** with GoConqr? Learn more.