En français, le mot informatique est bien souvent galvaudé.

Au quotidien, ce mot est fréquement assimilé à ``ordinateur muni de logiciels'', comme dans ``nous utilisons l'outil informatique pour simplifier l'administration'', ``l'informatique est en panne'' ou ``c'est la faute de l'informatique''. Ce n'est pas cette informatique-là qui fait l'objet de ce livre.

L'informatique est aussi une discipline universitaire. Malgré le mot ``science'' de la traduction anglaise ``computer science'', l'informatique n'est pas typiquement une science. En effet, le mot ``science'' est plus souvent associé à une discipline basée sur l'étude d'un phénomène réel, l'observation du phénomène et la construction de modèles l'expliquant le plus fidèlement possible.

Comme la mathématique, l'informatique n'étudie pas les phénomènes réels. Ces deux disciplines ont le privilège de pouvoir construire leur propre monde sous la forme d'objets abstraits. En mathématique, il s'agit de nombres, de relations, de fonctions, de transformations, etc. En informatique, on manipule (entre autres) des algorithmes, des programmes, des arbres, des preuves, des systèmes de réécriture, des images numériques et les vedettes de ce livre : les graphes.

L'informatique, comme d'autres disciplines, comporte plusieurs sous-disciplines ou domaines. Un sous-ensemble de ces domaines est l'informatique fondamentale. Certaines questions étudiées par l'informatique fondamentale sont directement utiles du point de vue pratique.
Exemples :

Algorithmique. Les méthodes les plus efficaces pour traiter un problème donné (trier un ensemble d'objets, trouver un objet minimal (sinon minimum) d'un ensemble, trouver un chemin d'un endroit à un autre, etc.).
Structures de données. La meilleure façon d'organiser un ensemble de données dans le but d'y accéder rapidement.
Complexité. Une façon d'exprimer l'efficacité d'un algorithme indépendamment d'un ordinateur ou d'un langage de programmation particuliers.
Certains autres domaines de l'informatique fondamentale sont plus théoriques.
Exemples :
Théorie des langages. Les différentes façons de produire et de reconnaître des suites de symboles ainsi que la difficulté d'écrire un programme réalisant ces opérations.
Calculabilité. Déterminer pour quels problèmes il est théoriquement possible d'écrire un programme qui le résout et pour quels problèmes ce n'est pas possible.
Logique. La puissance d'expression de différents types de logique et la correspondance avec d'autres systèmes formels.
D'autres domaines font partie de l'informatique pratique. Exemples :

Programmation. Techniques et méthodes pour organiser un programme de façon qu'il soit facilement modifiable (insertion facile de nouvelles fonctionnalités) sans risque d'introduction de défauts (en anglais : bugs).
Génie logiciel. Méthodes pour organiser le développement d'un logiciel de façon à obtenir un compromis acceptable entre qualité du produit final et coût du développement.
Informatique multimédia. Techniques et méthodes permettant d'analyser, de modifier et de synthétiser des images et des sons numériques de manière rapide et avec une qualité acceptable.
Systèmes d'exploitation. Techniques et méthodes pour réaliser un système d'exploitation qui assure intégrité, sécurité et performance.
Langages de programmation. Techniques pour construire un langage de programmation permettant d'exprimer facilement des algorithmes et facile à traduire en langage machine.
Compilation. Techniques pour construire un compilateur (programme qui traduit un programme écrit dans un langage en un autre langage, généralement moins évolué) de manière à ce que le programme généré soit efficace.

Suivant qu'on interprète cette question comme : ``pourquoi choisir une carrière en informatique?'' ou bien ``pourquoi étudier l'informatique alors qu'on a choisi une carrière différente (physique, chimie, mathématique, biologie, géologie, génie électrique, génie civil, etc.)?'', on trouve diverses bonnes raisons d'étudier l'informatique.
Tout d'abord, pourquoi choisir une carrière en informatique? Une première et séduisante raison est que cela donne une garantie d'embauche. L'effectif de l'industrie du logiciel ne cesse d'augmenter. Même les industries traditionnellement orientées vers des produits autres que le logiciel proprement-dit, recherchent de plus en plus d'informaticiens. La raison est simple : les produits de haute technologie comportent une part de plus en plus importante de logiciel. D'après Alcatel, ``60% du coût d'un téléphone portable est dû au logiciel''(cité par G. Kahn). Pour réaliser ces logiciels, l'industrie a besoin d'informaticiens ayant une bonne formation à la fois en informatique pratique (programmation, génie logiciel, compilation) et en informatique fondamentale (algorithmique, structures de données). De plus, les connaissances nécessaires pour produire ces logiciels suivent l'évolution de la complexité de ceux-ci, à savoir qu'elles augmentent chaque année. Dans un avenir proche, seules des études en informatique vont permettre la production efficace et économique de ces logiciels et, par conséquent, des produits dans lesquels ils sont intégrés. L'heure est peut-être venue de se débarrasser une fois pour toutes de l'image de l'informaticien passant 40-60 heures par semaine devant son écran, sans voir la lumière du jour et sans interaction avec ses collègues autrement que par courrier électronique. En fait, une carrière en informatique implique souvent de nombreux contacts avec d'autres informaticiens, avec des clients ou utilisateurs du logiciel final et avec des fournisseurs de matériel et logiciels. Ces contacts sont souvent internationaux, donnant l'occasion de voyager assez régulièrement. Même s'il y a de la place pour ceux qui préfèrent ne pas quitter leur l'écran, ce n'est pas la norme.

Maintenant, essayons de répondre à la question ``pourquoi étudier l'informatique alors qu'on a choisi une carrière différente?''. En fait, le travail d'un scientifique ou d'un ingénieur comprend de plus en plus l'utilisation d'un logiciel spécifique à son domaine, par exemple un logiciel de CAO (Conception Assistée par Ordinateur) ou un logiciel permettant de calculer les forces sur une construction. Souvent, un scientifique utilise un logiciel lui permettant d'éviter des calculs fastidieux. De nos jours, même un mathématicien utilise un logiciel de calcul formel pour des opérations symboliques comme l'intégration de fonctions ou la simplification d'expressions. Ces logiciels destinés à des utilisateurs scientifiques ou ingénieurs sont de plus en plus souvent programmables, à savoir qu'ils permettent à un utilisateur avancé d'ajouter des méthodes, calculs ou fonctionnalités non présentes dans la version initiale du logiciel. Même certains logiciels de bureautique, comme les tableurs, sont ainsi programmables. Pour que l'ingénieur ou le scientifique puisse se servir de manière efficace de ces logiciels, il doit avoir une formation de base en informatique. En l'absence d'une telle formation, il risque de mal programmer son logiciel, ce qui entrainera inefficacité et grosse perte de temps. La complexité des logiciels ne cesse d'augmenter  et entraine la nécessité d'une formation en informatique de plus en plus poussée des utilisateurs. De plus une culture de base en informatique lui permettra de dialoguer efficacement avec les informaticiens chargés de développer pour lui une application.

L'objet étudié dans ce livre, le graphe, est omniprésent dans un grand nombre de disciplines scientifiques et industrielles. Les graphes sont utilisés pour résoudre un grand nombre de problèmes comme l'allocation de ressources, l'installation optimale d'usines, l'optimisation des transports, l'ordonnancement de tâches, l'organisation optimale d'un travail, l'organisation de données pour une recherche rapide, etc. Une connaissance de base sur les graphes permet à un non-spécialiste en informatique d'accomplir son travail plus efficacement.

Bien qu'organisé essentiellement autour des graphes, ce livre apporte d'autres connaissances indispensables à un scientifique ou à un ingénieur. La notion d'algorithme, la connaissance d'algorithmes efficaces pour une panoplie de problèmes sont indispensables pour ces métiers. Un mauvais choix d'algorithme peut conduire à un programme nécessitant des années de calcul alors que le même problème aurait pu être résolu en quelques minutes sur la même machine.

Finalement, ce livre contient une partie concernant la programmation. Contrairement à ce que croient la plupart des gens, la programmation ne consiste pas uniquement à produire une suite d'instructions dans un langage donné pour résoudre un problème; ceci devrait d'ailleurs être dans les cordes de n'importe qui ayant une formation universitaire. L'essence de la programmation est plutôt une question d'organisation du programme. Pour comprendre cela, il est important de savoir que la plus grande partie (environ 80 %) du coût total d'un logiciel provient des modifications effectuées après la sortie de sa première version. On parle de maintenance du logiciel, souvent dûs à des changements des besoins de l'utilisateur. La programmation peut être vue comme une discipline dont le but est d'organiser le programme de façon à faciliter sa maintenance.

Tandis qu'il est relativement facile de faire fonctionner une première version d'un programme, il est très difficile de faire en sorte qu'elle soit maintenable. Ceci nécessite la connaissance de diverses techniques d'abstraction. Plusieurs techniques d'abstraction sont disponibles, en particulier l'utilisation de sous-programmes, de modules, de classes (programmation orientée-objets), d'extensions syntaxiques (macros), de fonctions de première classe, etc.

Il existe aussi plusieurs styles de programmation adaptés à différents types de problèmes (programmation impérative, symbolique, fonctionnelle, logique, etc.). Chaque style de programmation a ses propres idiomes nécessitant une formation spécifique.

Dans ce livre, nous allons parler uniquement de programmation impérative. Il s'agit de programmation basée essentiellement sur l'affectation de variables, de boucles et d'instructions conditionnelles.