Signed graphs

  1. Definition of signed graphs
  2. Balanced and partitionable signed graphs
  3. Inconsistency (error) of given partition of vertices
  4. Searching for optimal partitions using local optimisation


  1. Searching for the best partitions in
    • Sampson monastery:,,


  1. Each student gets his own signed graphs. Find partitions of signed graphs into 1, 2,n clusters (where n is number of vertices in the signed graph). For each number of clusters write the total error and number of optimal partitions. Draw a graph (number of clusters x error) for all three weeks in Excel. Report the partition where the total error is the lowest. Data

  2. Interpretation of results.

Slides (PDF)
Test signed graphs (ZIP)
Scores, assignments