163_Basic Graph Properties

A graph is a mathematical structure composed of a set of objects called vertices or nodes, and a set of connections called edges. A graph can be represented using the notation $G=(V,E)$, where $G$ stands for the graph, $V$ is the set of vertices, and $E$ is the set of edges. Here, edges represent the connections between nodes.

 

One of the most fundamental properties of a graph is whether it is directed or not. In th directed graph, also known as a digraph, each edge has a direction or orientation, connecting two nodes in a specific direction, where one node is the source and the other is the destination. Conversely, an undirected graph has edges without direction, indicating that the order of nodes is not important.

In Python, graphs can be conveniently defined using nx.Graph().

 

import networkx as nx
G = nx.Graph()
G.add_edges_from([('A','B'),('A','C'),('B','D'),('B','E'),('C','F'),('C','G')])
nx.draw_networkx(G)

 

 

Directed graphs can be represented using nx.DiGraph() in python

 

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([('A','B'),('A','C'),('B','D'),('B','E'),('C','F'),('C','G')])
nx.draw_networkx(G)

 

 

Another important property of graphs is whether the edges are weighted. In a weighted graph, each edge is associated with a weight or cost. These weights can represent various factors such as distance, travel time, or cost. Weights can be added to the edges of a previously defined undirected graph to modify it into a weighted graph.

 

import networkx as nx
G = nx.Graph()
G.add_edges_from([('A','B',{'weight':10}),
                  ('A','C',{'weight':20}),
                  ('B','D',{'weight':30}),
                  ('B','E',{'weight':40}),
                  ('C','F',{'weight':50}),
                  ('C','G',{'weight':60})])
pos = nx.spring_layout(G)
nx.draw_networkx(G,pos)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)