## Graphs, Dioids and Semirings: New Models and AlgorithmsThe primary objective of this essential text is to emphasize the deep relations existing between the semiring and dioïd structures with graphs and their combinatorial properties. It does so at the same time as demonstrating the modeling and problem-solving flexibility of these structures. In addition the book provides an extensive overview of the mathematical properties employed by "nonclassical" algebraic structures which either extend usual algebra or form a new branch of it. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

3 | |

22 Combinatorial Properties of Finite Semigroups | 6 |

23 Cancellative Monoids and Groups | 7 |

3 Ordered Monoids | 9 |

Examples | 11 |

33 Canonical Preorder in a Commutative Monoid | 12 |

34 Canonically Ordered Monoids | 13 |

63 The Maximum Capacity Path Problem and the Minimum Spanning Tree Problem | 159 |

65 The Shortest Path Problem | 160 |

68 The Kth Shortest Path Problem | 161 |

69 The Network Reliability Problem | 163 |

610 The ηOptimal Path Problem | 164 |

611 The Multiplier Effect in Economy | 165 |

613 Fuzzy Graphs and Relations | 166 |

614 The Algebraic Structure of Hierarchical Clustering | 167 |

35 HemiGroups | 17 |

37 Classiﬁcation of Monoids | 20 |

42 PreSemirings | 22 |

5 Semirings | 23 |

52 Rings and Fields | 24 |

53 The Absorption Property in PreSemiRings | 25 |

54 Product of Semirings | 26 |

6 Dioids | 28 |

62 Dioid of Endomorphisms of a Canonically Ordered Commutative Monoid | 31 |

63 Symmetrizable Dioids | 33 |

65 DoublyIdempotent Dioids and Distributive Lattices DoublySelective Dioids | 34 |

66 IdempotentCancellative Dioids SelectiveCancellative Dioids | 36 |

67 IdempotentInvertible Dioids SelectiveInvertible Dioids | 37 |

68 Product of Dioids | 38 |

69 Dioid Canonically Associated with a Semiring | 39 |

610 Classiﬁcation of Dioids | 40 |

Combinatorial Properties of PreSemirings | 51 |

2 Polynomials and Formal Series with Coefficients in a Pre Semiring | 52 |

22 Formal Series | 54 |

4 Bideterminant of a Square Matrix Characteristic Bipolynomial | 55 |

41 Reminder About Permutations | 56 |

42 Bideterminant of a Matrix | 58 |

43 Characteristic Bipolynomial | 59 |

5 Bideterminant of a Matrix Product as a Combinatorial Property of PreSemirings | 61 |

6 CayleyHamilton Theorem in PreSemirings | 65 |

7 Semirings Bideterminants and Arborescences | 69 |

72 Proof of Extended Theorem | 70 |

73 The Classical MatrixTree Theorem as a Special Case | 74 |

74 A Still More General Version of the Theorem | 75 |

8 A Generalization of the Mac Mahon Identity to Commutative PreSemirings | 76 |

81 The Generalized Mac Mahon Identity | 77 |

82 The Classical Mac Mahon Identity as a Special Case | 79 |

Topology on Ordered Sets Topological Dioids | 83 |

21 The SupTopology | 84 |

22 The InfTopology | 85 |

3 Convergence in the SupTopology and Upper Bound | 86 |

32 Concepts of Limitsup and Limitinf | 88 |

4 Continuity of Functions SemiContinuity | 89 |

5 The FixedPoint Theorem in an Ordered Set | 90 |

6 Topological Dioids | 91 |

QuasiInverse | 93 |

7 PStable Elements in a Dioid | 97 |

71 Examples | 98 |

72 Solving Linear Equations | 100 |

73 Solving Nonlinear Equations | 103 |

8 Residuation and Generalized Solutions | 107 |

Solving Linear Systems in Dioids | 115 |

2 The Shortest Path Problem as a Solution to a Linear System in a Dioid | 116 |

22 Bellmans Algorithm and Connection with Jacobis Method | 118 |

24 Minimality of BellmanJacobi Solution | 119 |

3 QuasiInverse of a Matrix with Elements in a Semiring Existence and Properties | 120 |

32 Graph Associated with a Matrix Generalized Adjacency Matrix and Associated Properties | 121 |

33 Conditions for Existence of the QuasiInverse A | 125 |

34 QuasiInverse and Solutions of Linear Systems Minimality for Dioids | 127 |

4 Iterative Algorithms for Solving Linear Systems | 129 |

42 Generalized GaussSeidel Algorithm | 130 |

43 Generalized Dijkstra Algorithm Greedy Algorithm in Some Selective Dioids | 133 |

44 Extensions of Iterative Algorithms to Algebras of Endomorphisms | 136 |

Generalized GaussJordan Method and Variations | 145 |

Algorithms | 151 |

53 Generalized Escalator Method | 152 |

An Overview of Pathﬁnding Problems in Graphs | 156 |

61 Problems of Existence and Connectivity | 158 |

Linear Dependence and Independence in SemiModules and Moduloids | 173 |

22 Morphisms of SemiModules or Moduloids Endomorphisms | 175 |

23 SubSemiModule Quotient SemiModule | 176 |

25 Concept of Linear Dependence and Independence in SemiModules | 177 |

3 Bideterminant and Linear Independence | 181 |

31 Permanent Bideterminant and Alternating Linear Mappings | 182 |

General Results | 184 |

The Case of Selective Dioids | 187 |

34 Bideterminant and Linear Independence in SelectiveInvertible Dioids | 192 |

35 Bideterminant and Linear Independence in MaxMin or MinMax Dioids | 200 |

Eigenvalues and Eigenvectors of Endomorphisms | 207 |

General Results | 208 |

3 Eigenvalues and Eigenvectors in Idempotent Dioids | 212 |

4 Eigenvalues and Eigenvectors in Dioids with Multiplicative Group Structure | 220 |

42 The PerronFrobenius Theorem for Some SelectiveInvertible Dioids | 227 |

5 Eigenvalues Bideterminant and Characteristic Bipolynomial | 231 |

6 Applications in Data Analysis | 233 |

61 Applications in Hierarchical Clustering | 234 |

A Few Answers to the Condorcet Paradox | 238 |

Dynamic Linear System Theory | 242 |

71 Classical Linear Dynamic Systems in Automation | 243 |

72 Dynamic Scheduling Problems | 244 |

74 Timed Event Graphs and Their Linear Representation in R Max+ and R +min+ | 247 |

75 Eigenvalues and Maximum Throughput of an Autonomous System | 251 |

Dioids and Nonlinear Analysis | 257 |

2 MINPLUS Analysis | 261 |

3 Wavelets in MINPLUS Analysis | 268 |

4 InfConvergence in MINPLUS Analysis | 271 |

5 Weak Solutions in MINPLUS Analysis Viscosity Solutions | 278 |

6 Explicit Solutions to Nonlinear PDEs in MINPLUS Analysis | 283 |

The HopfLax Formula | 288 |

7 MINMAX Analysis | 291 |

72 InfConvergence in MINMAX Analysis | 293 |

73 Explicit Solutions to Nonlinear PDEs in MINMAX Analysis | 294 |

74 Eigenvalues and Eigenf unctions for Endomorphisms in MINMAX Analysis | 295 |

8 The Cramer Transform | 298 |

Collected Examples of Monoids PreSemirings and Dioids | 313 |

11 General Monoids | 314 |

12 Groups | 318 |

13 Canonically Ordered Monoids | 319 |

14 HemiGroups | 323 |

15 Idempotent Monoids SemiLattices | 325 |

16 Selective Monoids | 328 |

2 PreSemirings and PreDioids | 331 |

21 Right or Left PreSemirings and PreDioids | 332 |

22 PreSemiring of Endomorphisms of a Commutative Monoid | 335 |

23 PreSemiring Product of a PreDioid and a Ring | 336 |

24 PreDioids | 337 |

3 Semirings and Rings | 338 |

31 General Semirings | 339 |

32 Rings | 340 |

4 Dioids | 341 |

42 Dioid of Endomorphisms of a Canonically Ordered Commutative Monoid Examples | 345 |

43 General Dioids | 348 |

44 Symmetrizable Dioids | 351 |

45 Idempotent Dioids | 353 |

46 Doubly Idempotent Dioids Distributive Lattices | 357 |

47 IdempotentCancellative and SelectiveCancellative Dioids | 358 |

48 IdempotentInvertible and SelectiveInvertible Dioids | 361 |

367 | |

377 | |

### Other editions - View all

Graphs, Dioids and Semirings: New Models and Algorithms Michel Gondran,Michel Minoux No preview available - 2010 |

Graphs, Dioids and Semirings: New Models and Algorithms Michel Gondran,Michel Minoux No preview available - 2008 |

### Common terms and phrases

algebraic structure algorithm arcs assume bideterminant canonical order relation canonical preorder relation canonically ordered monoid Cayley–Hamilton theorem Chap classical columns commutative monoid components convergence convex corresponding deduce deﬁned Deﬁnition denoted det+(A distributive lattice eigenvalue eigenvector endomorphisms endowed equation Example exists ﬁnite ﬁrst free monoid function f Gondran graph G hemi-group idempotent dioid idempotent monoid integer iteration left distributivity Lemma Let us consider matrix minimal solution MINMAX Minoux Mn(E neutral element nondecreasing observe obtain operation ordered set p-stable Perron–Frobenius theorem Petri net polynomial pre-dioid pre-semiring Proof properties Proposition quasi-inverse real numbers resp Right and left satisﬁes satisfying Sect selective dioid selective-invertible dioid semi-module semigroup semiring sequence shortest path problem spectral radius subset Sup-topology Theorem topological dioid Total order upper bound vector vertex vertices viscosity solutions