About Book

Graph theory, in mathematics and computer science, is the study of graphs, which are mathematical structures, used to model pair wise relations between objects. Emphasizing their application to real-world systems, the term network is sometimes defined to mean a graph in which attributes are associated with the vertices and edges, and the subject that expresses and understands the real-world systems as a network is called network science. Today, graph theory is an important analysis tool in mathematics and computer science. Because of the inherent simplicity of graph theory, it can be used to model many different physical and abstract systems such as transportation and communication networks, models for business administration, political science, and psychology and so on. Another important concept in graph theory is the path, which is any route along the edges of a graph. This book is a valuable compilation of topics, ranging from the basic to the most complex theories and principles in the field of graph theory. It deals with spectral graph theory, graph theory in managing power, electric power systems, linear graph theory, survivability design, topology control, production process, new perspectives with graph theory, graph labelling and graph theory approaches. This book attempts to understand the multiple aspects of graph theory and how such concepts have practical applications. Some of the diverse topics covered in this book address the varied branches that fall under this category. The book is envisioned for both researchers in fields such as mathematics, computer science, system science, and as a reference tool for professionals and practitioners.

Preface............................................................................................................v

Chapter 1 Decision-Making in Real-Life Industrial Environment through Graph Theory Approach...........................................................................1

Abstract ...............................................................................................1

1. Basic overview of graph theory.........................................................2

2. Selection of attributes...........................................................................3

3. Case studies on graph theory: a view on real-life problem

solving.....................................................................................................7

4. Conclusions..........................................................................................14

Chapter 2 An Example Usage of Graph Theory in Other Scientific Fields: On Graph Labeling, Possibilities and Role of Mind/Consciousness....18

Abstract.................................................................................................18

1. Introduction..........................................................................................18

2. Resolving aspects of paranoid schizophrenia...............................20

3. Role of mind and consciousness in resolving the graceful tree

conjecture..............................................................................................30

4. Graph labelings and applications....................................................35

5. Results in graph labelings using computer software..................41

6. Lexicographic order in graph labelings..........................................43

7. Conclusion............................................................................................45

Chapter 3 The Assembly of Protein Oligomers — Old Stories and New Perspectives with Graph Theory...........................................................49

1. Introduction..........................................................................................49

2. Overview of protein assembly.........................................................53

3. Intermolecular and intramolecular amino acid interactions:

The mechanism of protein assembly..............................................65

4. Local key contacts regulate global conformations.......................72

5. Conclusion............................................................................................77

Chapter 4 Study of Changes in the Production Process Based in Graph

Theory..........................................................................................................95

1. Introduction..........................................................................................95

2. The production cycle model for short life cycle models............96

3. Product life cycle and production cycle ....................................103

4. A production management model for short life-cycle goods..106

5. A study of changes in the production process for short-life

cycle goods ......................................................................................113

6. Conclusion .........................................................................................120

Chapter 5 Applied Graph Theory to Improve Topology Control in Wireless

Sensor Networks.....................................................................................125

1. Introduction........................................................................................125

2. Wireless Sensor Networks...............................................................127

3. Domination in graph theory...........................................................128

4. Clustering and topology control....................................................129

5. Centralized (k, r)-CDS mechanism................................................131

6. Distributed (k, r)-CDS mechanism................................................134

7. Performance analysis........................................................................138

8. Conclusion..........................................................................................142

Chapter 6 Graph Theory for Survivability Design in Communication

Networks...................................................................................................145

1. Introduction........................................................................................145

2. Chapter outline..................................................................................146

3. Graph connectivity in relation to network protection design.147

4. Establishing physical survivability................................................148

5. Graph algorithms for diverse routing in protection design.....155

6. Conclusion..........................................................................................161

Chapter 7 Simulation of Flexible Multibody Systems Using Linear Graph

Theory........................................................................................................163

1. Introduction........................................................................................163

2. System representation by linear graph.........................................164

3. Virtual work terminal equations for rigid bodies......................172

4. Flexible multibody systems (FMS)................................................179

5. Examples.............................................................................................187

6. Conclusion..........................................................................................190

7. Acknowledgement.............................................................................191

Chapter 8 Research Progress of Complex Electric Power Systems:

Graph Theory Approach.......................................................................194

1. Introduction........................................................................................194

2. Electric circuit theory.......................................................................195

3. Search principles in graph theory.................................................197

4. Cluster analysis.................................................................................199

5. Fault analysis based on BFS and DFS..........................................200

6. Fault analysis based on hierarchical cluster analysis................202

7. New approach for finding connected routes of power

network...............................................................................................204

8. The new connected routes finding algorithm.............................205

9. The application for substation configuration of power system

topology analysis...............................................................................210

10. Conclusion..........................................................................................212

11. Acknowledgements...........................................................................213

Chapter 9 Application of the Graph Theory in Managing Power Flows in

Future Electric Networks......................................................................216

1. Introduction .....................................................................................216

2. Power flow management.................................................................217

3. Power routing – A new way for power flow management.....219

4. Graph-based algorithms...................................................................221

5. Agent-based implementation..........................................................226

6. Simulation results and discussions................................................229

7. Conclusion..........................................................................................233

Chapter 10 A Semi-Supervised Clustering Method Based on Graph Contraction

and Spectral Graph Theory..................................................................236

1. Introduction........................................................................................236

2. Semi-supervised clustering..............................................................238

3. Graph-based semi-supervised clustering.....................................239

4. Evaluations.........................................................................................245

5. Discussions.........................................................................................253

6. Conclusion..........................................................................................254

7. Acknowledgments.............................................................................254

Citation......................................................................................................259

Index...........................................................................................................261

About Author

Earnestine Prafull obtained her Ph.D. in Computer Science from Public Research University, Albury. She has written pioneering papers on enumerative techniques in topological graph theory. Her expertise includes topology, graph theory, and discrete mathematics. She is a Guest Lecturer at University College, Ajman. Her research focuses on data organization, computational devices, graph theory, algorithmic graph theory, cryptology and computer algebra, logic, games, and information dynamics, etc. Prafull is on the editorial board of several renowned mathematical journals. She consistently shares her knowledge with the student fraternity by organizing lectures and conferences across the globe.